[백준]1874번 스택 수열 - 스택

 

n = int(input())
list=[]
cnt = 1
stack = []
result = []
temp = True
for i in range(n):
    list.append(int(input()))
for i in range(n):
    while cnt <= list[i]:
        stack.append(cnt)
        result.append("+")
        cnt += 1
    if stack[-1] == list[i]:
        stack.pop()
        result.append("-")
    else :
        temp = False
        break
if temp == False:
    print("NO")
else :
    for i in range(len(result)):
        print(result[i])

 

코드 설명

반복문을 통해 먼저 값을 빈 리스트에 넣어준다. 다시 한번 반복문을 돌며 리스트 안의 값이 카운트보다 작아질 때까지 반복한다. 카운트 값을 스택에 넣어주고 결과 리스트에도 "+" 를 넣어준다.

만약, 스택의 맨 위의 원소가 리스트의 원소와 동일하다면 pop() 연산과 결과 리스트에 "-"를 저장한다. 일치 하지 않을 경우에는 temp = False 값을 할당한다.

temp == False 일 경우는 "NO", 아니라면 결과 리스트를 출력하여준다.

 

Point: 스택에 push 할 경우에는 오름차순을 지켜야 하므로 cnt 변수를 활용하여 준다. while문을 진행하다가 list[i] 값과 스택의 최상위 원소가 같을 경우에는 수열을 만들기 위해 스택에서 cnt를 pop 한다. 원소가 같지 않은 경우에는 수열이 불가능 하므로 NO 를 출력하게 한다.