[백준] 파이썬 python - 1874번 : 스택 수열

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

1874번: 스택 수열

1874번: 스택 수열

레벨 실버 2. 스택 / 자료 구조

 

 

접근 방식
1. 가장 먼저 입력받았을 경우
 - 해당 숫자까지 오름차순으로 stack에 push(+) 한 후, 해당 숫자를 pop(-) 한다. 
2. stack이 비었지만, stack에 저장한 경력이 있을 경우
 - 마지막으로 push한 숫자부터, 현재 입력받은 숫자까지 stack에 push(+)한 후, 해당 숫자를 pop(-) 한다.
3. 현재 입력받은 숫자와 stack의 top 숫자가 일치할 경우
 - 해당 숫자를 stack에서 pop(-)한다.
 4. stack이 비지 않았으며, 입력받은 숫자가 한번도 stack에 저장된 적 없을 경우
 - 마지막으로 push한 숫자부터, 현재 입력받은 숫자까지 stack에 push(+)한 후, 해당 숫자를 pop(-) 한다.
5. 위의 모든 과정이 끝난 후, stack이 비었다면 가능한 경우이므로 push와 pop의 결과를 출력한다.
6. stack이 비지 않았다면 불가능한 경우이므로 "NO"를 출력한다.

 

 

코드

import sys
input = sys.stdin.readline

stack = []
n = int(input())
result = []
now = 0 # 스택에 넣은 마지막 숫자를 저장

for i in range(1, n+1) :
    num = int(input())

    if now == 0 and len(stack) == 0 : # 가장 먼저 입력받은 숫자
        for j in range(num):
            stack.append(j+1)
            result.append("+")
            now = num
        result.append("-")
        stack.remove(num)

    elif now != 0 and len(stack) == 0 : # 스택이 비었지만, 초기상태는 아닐 때
        for j in range(now+1, num+1) :
            result.append("+")
            stack.append(j)

        stack.remove(num)
        result.append("-")

        now = num

    elif len(stack)!= 0  and stack[-1] == num: # 입력받은 숫자와 스택의 top이 일치할 때
        stack.remove(num)
        result.append("-")

    elif len(stack)!= 0 and num > stack[-1] : # 입력받은 숫자가 한번도 stack에 들어온 적 없었을 때
        for j in range(now+1, num+1) :
            result.append("+")
            stack.append(j)
            now = num
        stack.remove(num)
        result.append("-")

if len(stack) == 0 : #스택이 비었을 때는 가능
    for i in result:
        print(i)

else: #스택에 숫자가 남아있을 경우는 불가능
    print("NO")

 

처음엔 봤을 때 조금 당황스러웠는데 조금만 생각하니까 답이 나왔다.

나 어쩌면 성장한 거일지도

사실 스택이나 자료 구조 문제는 좀 풀기 수월한 것 같다. 실버2를 잘 풀었음에 감사합니다..