[백준] 1874번 - 스택 수열 (By Python)

 

풀이과정

힌트를 참고하면 문제를 쉽게 이해할 수 있다.

N이 8이라고 가정할 때, 입력된 수열 [4,3,6,8,7,5,2,1]을 구하는 과정은 다음과 같다.

 

먼저 1부터 8까지의 숫자를 넣기 위한 리스트와, push,pop 연산을 각각 '+'와 '-'로 나타내기 위한 스택 리스트를 생성한다.

1부터 4까지 먼저 리스트에 push한 후, 4,3을 pop한다. 그러면 리스트 내부에는 [1,2]만 남게 된다.

 

이후 6까지 push 한 후 다시 pop을 해주는데 여기서 문제가 발생한다. 다시 1부터 6까지 리스트에 push하게 되면 리스트 내부에는 [1,2,3,4,5,6]이 남게 되고,pop을 수행하면 [1,2,3,4,5]가 남게 된다.8까지 push한 후 pop연산을 수행하면 위의 순서대로 연산이 나오지 않을 뿐더러 3,4 가 중복해서 수열에 들어가는 오류가 발생한다. 따라서 밑의 코드처럼 지금까지 push된 숫자를 확인해주는 변수를 추가해 문제를 해결한다.

 

밑의 count 변수는 4를 push할 때 while문을 통해 5까지 증가하였다. 이후 n=6일때 반복문이 실행되지만, 이미 count는 5까지 증가되 있으므로 리스트에는 5,6 만 추가되게 된다. 이후 6이 pop되고, 다시 8까지 push 한 후 남은 원소들을 전부 pop하면 위의 수열이 출력되게 된다.

 

또한 문제에서는 'NO'가 출력되는 사례로 N = 5, 수열 = {1,2,5,3,4}를 제시했는데, 왜 반례가 성립하는지도 알아보자.

1,2를 push하고 pop한 이후, 5까지 push 한다. 이 때, 리스트에는 [3,4,5]가 들어가게 되는데, pop을 수행하게 되면

[5,4,3] 순서대로 출력되고, [5,3,4] 순서대로는 출력될 수 없다. 따라서, 위의 케이스는 성립하지 않는다.  

 

코드

N=int(input())
list=[]       # 1부터 N까지의 숫자를 넣기 위한 리스트
stack=[]   # push, pop을 각각 '+','-'로 치환해 삽입하기 위한 리스트
count=1   # 숫자의 중복을 막기 위한 변수
temp=True   # 출력 가능한 순열인지를 확인하기 위한 변수
for i in range(N):
    num=int(input())
    while count<=num:        
        list.append(count)
        count+=1
        stack.append('+')
    if list[-1]==num:
        list.pop()
        stack.append('-')
    else:
        temp=False
if temp==False:
    print("NO")
else:
    for i in stack:
        print(i)