[Python]백준 1874 ::스택수열 문제 풀이

뭘 사용? 스택 두개

 

어떻게 접근 하고 어떤 것이 중요했나?

스택1은 값들을 넣는 스택이고 스택2는 스택1에서 팝해와서 만들어야 하는 수열을 만드는 스택이다.

먼저, 만들어야 하는 주어진 수열에 pinindex를 설정해서, 해당하는 인덱스의 값을 스택 1에서 찾을 수 있는지를 보고,

없다 하면 1부터 차례대로 추가해준다.

만약에 스택1에 있다면 젤 마지막 값이 원하는 값인지를 보는데, 만약 원하는 값이면 스택1에서 팝해서 스택 2에 넣으면 된다.

만약에 아니면 그건 만들 수 없는 수열이 된다.

 

 

구현 코드( 주석 부분은 어떻게 동작하면 되는지 파악 할때 쓰였다.)

n = int(input())

stk_n = [] # 이 수열을 만들어야 함 [4,3,6,8,7,5,2,1]
stk_1 = [] 
stk_2 = []
result = []
for i in range(n):
    stk_n.append(int(input()))
    
''''
[1,2,3,4]++++  [4,3]--
[1,2,5,6]++        [4,3,6]-
[1,2,5,7,8]++    [4,3,6,8,7,5]---
[1,2]            [4,3,6,8,7,5,2,1]--
'''

pin = 0
i = 1

while(True):
    
    if(pin <= n-1):
        pin_num = stk_n[pin] 

        if(pin_num not in stk_1):
            stk_1.append(i)
            result += '+'
            i += 1

        else:
            if(stk_1[-1]== pin_num):
                stk_2.append(stk_1.pop(-1))
                result+='-'
                pin+=1
            else:
                result = 'NO'
                break
                
    else:
        break


if(result == 'NO'):
    print(result)
else:
    for j in range(len(result)):
        print(result[j])