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

코드

num = int(input()) #원소가 몇 개 있는지
original_list = [] # 원래 주어지는 배열
for i in range(num):
    a = int(input()) #리스트의 원소들
    original_list.append(a)
# print(original_list)
ordered_list = sorted(original_list) #오름차순 정렬한 배열


stack = [] 
origin_index = 0 #원래 배열과 비교하기 위한 변수
push_pop=[] #연산을 저장하는 배열
for index in range(len(ordered_list)):
    stack.append(ordered_list[index])
    push_pop.append('+')
   
    for i in range(len(stack)):
        if stack[-1]==original_list[origin_index]:
            stack.pop()
            push_pop.append('-')
            origin_index+=1
        else:
            break

if not stack :
    for i in push_pop:
        print(i)
else:
    print('NO')

풀이

8개의 수가 입력이 된다.

이 수들을 이용해 수열이 만들어졌는데

어쩌고 저쩌고 팝이랑 푸시를 해서 원래 수열을 만들수 있냐는 것이다

그러니까 처음 주어진 수열은 [4,3,6,8,7,5,2,1]인데

여기서 오름차순으로 1부터 ~8까지 순서대로 푸시를 하고 팝을 하면서

처음 주어진 수열을 만들 수 있냐는 것!

오름차순으로 푸시를 하라고 했으니 임의의 수열에 [1,2,3,4]가 푸시될 것이고

4가 나왔으니 pop해서 처음 수열과 똑같은 수열을 만들려고 정의해놓은 새로운 리스트에 4를 넣고

[1,2,3]이 남았는데 또 3을 pop해서 새로운 리스트에 3을 넣어서 [4,3]을 만들고.......

이렇게 이루어진다.

 

받은 수들을 original_list로 만들어주었다.

그리고 오름차순으로 push할 수 있다고 해서 sorted를 통해서 정렬을 해주었는데

어짜피 1에서부터 num까지의 수가 나오니까 꼭 이걸 안해도 된다.

 

 

stack에 오름차순으로 순서대로 넣고 push_pop 배열에 +를 저장한다.

그리고 스택의 마지막 수가 original_list의 값과 같은 것이 나온다면 pop하고 -를 저장한다

orginal_list의 인덱스 0부터 비교하고 같은게 나올때마다 index를 +1해준다

 

 

stack이 다 비워졌으면

push_pop배열을 순서대로 출력하고

그렇지 않으면 NO를 출력한다.

스택이 다 비워졌지 않다는 것은 위에 for문을 돌면서

오리지널 리스트랑 같은 값을 매칭 못해서 pop을 못했다는 뜻이기 때문이다.