백준 1874번 - 스택 수열 [python]

Python 코드

n = int(input())
nums = [] # 입력 받은 수열 담을 리스트
stack = [] # 스택 자료구조를 구현한 리스트
res = []  # push와 pop 연산을 저장할 리스트
num_idx = 0 # 수열 현재 위치

for i in range(n):
    num = int(input())
    nums.append(num)
print(nums)
for i in range(1, n+1): # stack에 1~n 까지 숫자를 차례대로 push, push 수행 할때마다 'res'에 '+' 추가
    stack.append(i)
    res.append('+')

    while stack and stack[-1] == nums[num_idx]: # stack이 비어있지 않고, stack의 top 값이 수열(nums) 현재 위치 값과 같을때
        stack.pop() # stack에서 pop 수행할 때마다 'res'에 '-' 추가
        res.append('-')
        num_idx += 1 # pop 수행 후 수열의 다음 위치로 이동

if not stack: # 스택이 비어있는지 확인 후 결과 출력
    print("\n".join(res)) # 비어있으면 res 출력
else: # 비어있지 않다면 수열을 만들 수 없으니 'NO' 출력
    print("NO")

Python 코드 풀이

1. 코드에 대한 전체적인 풀이

문제는 1부터 n까지의 수를 스택에 push와 pop을 하여 주어진 수열을 만들 수 있을지, 그리고 만들 수 없다면 "NO"를 출력하라는 것이었습니다.

먼저, nums 스택에 0부터 n까지의 숫자를 push하였습니다. (이때, nums 스택에는 입력한 숫자가 모두 포함되게 됩니다. 이 스택은 비교를 위해 생성하였습니다.)

다음으로, 주 스택에 1부터 n까지의 숫자를 push하면서 매 push할 때마다 결과 문자열(res)에 '+'를 추가하였습니다.

스택의 top 값이 수열의 현재 위치와 같다면, pop을 수행하면서 수열의 포인터를 다음 위치로 이동시켰습니다. 이때도 마찬가지로 pop 수행할 때마다 결과 문자열(res)에 '-'를 추가하였습니다.

만약 스택의 top 값이 수열의 현재 위치와 다르다면, 현재 위치의 값이 될 때까지 숫자를 push하였습니다.

마지막으로, 스택이 비어 있지 않다면 주어진 수열을 만들 수 없는 것으로 판단하였습니다.

시간 복잡도 측면에서 보면, 각 수열의 개수에 따라 push와 pop 연산을 수행하므로 시간 복잡도는 O(N)이 됩니다.

혹시 더 궁금한 점이 있으시다면 언제든지 알려주세요!