[Python] 백준 1874 스택 수열

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

     

    1874번: 스택 수열

    1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

    www.acmicpc.net

     

    문제

     

    해설

     

    처음에 풀 때 문제 이해가 잘 안되었다.. 결국 어떤 분의 설명을 블로그에서 읽고 겨우 이해했는데

    만약 처음으로 4를 입력했다면

    • 내가 첫 번째로 pop한 숫자가 4가 되어야 하고, 그러기 위해서는 1,2,3,4가 이미 스택안에 있어야 한다.
    • 그래서 입력한 수를 만날 때 까지는 계속 push를 해서 1,2,3,4가 스택에 있도록 해야한다.

     

    그래서 예제 입력을 하나씩 뜯어보자!

    # 예제 입력
    8 # 첫줄에 입력받을 수의 개수인 n을 입력받음
    
    4 # 내가 처음 pop하고 싶은 수가 4임 그렇다면 1, 2, 3, 4까지 스택에 있어야함 
    	# 그러므로 push 4번 해주어야 함 [ + + + + ]
    	# 그후 4를 pop [ - ]
    3 # 3은 지금 스택에 1,2,3이 있으니 바로 pop가능 [ - ]
    6 # 6은 스택에 1,2가 있으니까 5, 6 푸쉬하고 6을 pop해야 하므로 [+ + -]
    8 # 8은 스택에 1,2,5 있으니까 7, 8 푸쉬하고 8을 pop해야하므로 [+ + -]
    7 # 7은 바로 pop 가능 [ - ]
    5 # 바로 pop 가능 [ - ]
    2 # 바로 pop 가능 [ - ]
    1 # 바로 pop 가능 [ - ]

     

    코드

    n = int(input())
    
    count = 0
    stack = []
    result = []
    msg = True
    
    for i in range(n):
        x = int(input())
        
        while count < x: # 내가 입력한 수까지 푸쉬를 해주자
            count += 1
            stack.append(count)
            result.append('+') # 푸쉬를 했다면 result 변수에 + 추가
    
        if stack[-1] == x: # 스택의 맨 위의 값이 내가 pop하고자 하는 값과 같으면
            stack.pop() # pop
            result.append('-') # - 저장
        else:
            msg = False
            exit(0)
    
    if msg == False:
        print("NO")
    else:
        print("\n".join(result))

    댓글