백준 - 스택 수열 1874

https://www.acmicpc.net/problem/1874

문제 해석

위 예제처럼 n이 8로 주어졌다고 할때, 1~8를 pop과 push를 이용해 입력으로 들어온 값과 같은 순서로 정렬하면 되는 문제다. 이때 push는 +로, pop은 -로 출력한다.

 

위 예제처럼 4가 들어오면 빈 리스트에 1,2,3,4 까지 push를 이용해 리스트에 넣어주면 [1,2,3,4]가 된다. 여기서 4를 pop하면 [1,2,3]이 되고, 그 다음으로 입력받은 값은 3이므로 pop하면 [1,2]... 이런식으로 진행하면 된다.

 

 

다만 여기서 주의해야 하는 경우는 불가능한 경우인데, 아래 예제를 한번 보며 설명해보려 한다.

 

일단 1를 push 하고 pop 한다.  2도 push하고 pop 하면된다. 이 다음 5를 입력받았으므로 리스트에 [3,4,5]까지 넣어주고 5를 pop한다. 근데 그 다음으로 입력받은 값이 3인데, 바로 뒤에는 4가 있어서 pop을 못하게 된다. 이게 불가능한 경우이다.

 

따라서 입력받은 값이 전의 수보다 크거나, 바로 전에 있는 값이 아니면 불가능한 경우가 된다.

 

코드 구상

일단은 숫자를 전부 입력받아 리스트로 만든다. 그 리스트로 for문을 돌리며 여태껏 나왔던 수보다 작으면 전에 것과 같은지 판단하고, 여태껏 나왔던 수보다 크다면 push를 통해 숫자를 키워준다.

 

코드

# 1874 스택수열
n = int(input()) #n값 받아서
n_list = [int(input()) for _ in range(n)] #숫자
#print(n_list)
stack_list = [] #스택 리스트 만들어주고

print_stack = [] #프린트할 리스트 만들어 주고
count = 1 #카운트로 기준값 설정

no = 0 #이미 no를 출력했는지 확인
for number in n_list: #숫자 리스트중 하나씩 뽑아서
    if(number<count-1): #만약 카운트-1(전의 number값)보다 작고
        if(stack_list[-1]==number): #리스트의 마지막 값과 같다면
            print_stack.append('-') #-출력
            stack_list.pop() #리스트 마지막 요소 pop
        else: #리스트의 마지막 값과 같지 않다면
            no = 1 #no값을 1로 만들고
            print('NO') #no프린트후
            break #빠져나가기
    else: #만약 전의 number값보다 작지 않다면
        for i in range(count,n+1): #카운트값~n+1사이로 for을 돌리면서

            if(i==number): #만약 number와 값이 일치한다면
                print_stack.append('+') #i라는 값이 들어간 후 빠지는 것이기 때문에 +를 넣어주고
                print_stack.append('-') #-라는 값을 넣어주고
                break #다음 number로 넘어감
            else:
                stack_list.append(i) #number와 i의 값이 일치하지 않는다면
                print_stack.append('+') #+를 추가해주고 i값을 키워줌
    if(count<number+1): #만약 count값이 number+1(number 다음부터 시작해야 하니깐) 작으면
        count = number+1 #카운터 값을 number+1값으로 함
if(no==0): #만약 중간에 no를 출력하지 않았다면
    for i in print_stack: #print_stack을 돌면서
        print(i) #프린트