[백준] 1874번 : 스택 수열 (파이썬)

문제

나의 답안

n=int(input()) 
sta=[] #스택 배열
cnt=1 # 입력하려는 수보다 작은 숫자(증가)
result=[] # +/-를 저장할 배열
status=True # 스택이 만들어질 수 없을 때, 즉 NO일 때를 판별하기 위한 boolean값

for i in range(n):
    num=int(input())
    while cnt<=num:
        sta.append(cnt)
        result.append('+')
        cnt+=1
    if sta[-1]==num:
        sta.pop()
        result.append('-')
    else:
        print('NO')
        status=False
        break

if status:
    for i in result:
        print(i)

문제를 이해하는데 오래걸렸다.

접근방법

• 문제에서 '스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자' 라고 하였으므로 입력하려는 수보다 큰 수가 스택 안에 존재하면 안된다.
• 또한 해당조건에 따라, 4가 입력되려면 4보다 작은 1, 2, 3이 전부 스택안에 저장되어야 하므로 1~3을 모두 push해주어야 한다. sta=[1,2,3]
• 계속 push하다가 4가 된다면 4를 pop해준다. sta=[1,2,3,4] => sta=[1,2,3]
• 예제에서 4를 입력한 후 3이 나온다. 4를 pop한 후에 3을 만났을 때는 찾는 값이 스택의 top값이므로, 더 push할 필요가 없고 바로 pop을 해주면 된다. sta=[1,2]
• 이후 6이 나오는데, 3과 4는 이미 pop을 한 상태이므로 6이 입력될 때는 5, 6을 push하고 6을 pop한다. sta=[1,2,5,6] => sta=[1,2,5]
  
  

1. 각 변수를 선언한다.
2. 반복문으로 n번 반복하면서 수열을 이루는 정수(num)를 입력받는다.
3. while문으로 sta에 cnt를 추가하고(push) result에 +를 추가한 후 cnt를 1씩 증가시킨다. cnt가 num보다 커질 때까지 반복한다.
4. 만약 sta의 top값이 num과 같아진다면, 입력하려는 숫자를 만난 것이므로 pop을 해주고 -를 배열에 저장한다.
5. 만약 sta의 top값이 num보다 크다면 state변수를 false로 바꾸고 반복문을 빠져나온다.(status변수가 없다면 결과 출력 시 올바른 스택 수열이 아니어도 result배열의 값을 출력하게 된다.)
6. status변수가 true면 배열을 출력한다.