[ 파이썬(python) ] 백준 1874 - 스택 수열

📍 백준 1874 - 스택 수열

문제: 백준 1874 - 스택 수열

---

💡 나의 풀이

나에겐 난이도가 있던 문제였다. 문제의 길이는 짧았지만 이해하기까지 시간이 오래 걸렸다.

 

중요한 포인트는 스택에 push하는 순서는 반드시 오름차순을 유지한다.라는 문장인데, 이를 다시 말하면 push 순서는 현재 만들어야 할 수열보다 작아질 수 없고 오직 current = target 혹은 current > target 할때만 성립한다는 의미다. 이를 이해하기까지는 꽤 오랜 시간이 걸렸다. 

 

또, current는 어떻게 구현해야하지를 고민했는데 1~n까지 선언한 다음 여기서 뽑지 않은 값 중 가장 작은 값들을 가져와야 하는 건가? 생각했는데 결론적으로 current += 1씩 증가하면서 값을 넣으면 된다.

 

1. current가 target보다 작거나 같을 때 까지 current를 stack에 넣어준다. (push 연산)
2. 만약, stack[-1]이 target과 같다면 pop 연산을 수행한다.
3. 연산이 끝났을 때 stack에 아무것도 남아있지 않다면 push, pop 연산을 출력한다.
4. 연산이 끝났는데도 stack이 남아있거나 current > target이면 NO를 출력한다.

 

 

# 나의 풀이
import sys
input = sys.stdin.readline

n = int(input())
targets = [int(input()) for _ in range(n)]

flag = True
stack, answer, current = [], [], 0

for target in targets:
    while True:
        if stack and stack[-1] == target:    # stack: 을 작성한 이유는 맨 처음 stack은 아무것도 없기 때문
            answer.append('-')
            stack.pop()
            break

        elif current > target:
            flag = False

        else:
            current += 1
            stack.append(current)
            answer.append('+')

        if not flag:
            print('NO')
            exit()

if flag:
    print('\n'.join(answer))

# 다른 사람의 풀이
import sys
input = sys.stdin.readline

n = int(input())
targets = [int(input()) for _ in range(n)]
current = 1
stack, answer = [], []

for target in targets:
    while current <= target:
        stack.append(current)
        answer.append('+')
        current += 1

    if stack[-1] == target:
        answer.append('-')
        stack.pop()

if not stack:
    print('\n'.join(answer))
else:
    print('No')