[BOJ] 1874: 스택 수열 (python)

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

 

문제

 

문제 이해 하는 데에만 5분? 걸렸다. (이럴 때 마다 자괴감 듦..)
사실 문제를 제대로 잘 안읽어서 그랬던 거다.

아직 코테 공부 초기이니 하다보면 문제 읽는 거, 핵심 파악하는 거, 전부 늘겠거니 생각하고 있다.

---

1부터 N까지의 수를 스택에 넣었다가 다시 빼서 수열을 만들었을 때, 입력으로 넣은 수열을 만들 수 있느냐. 임

index 비교해서 +하고 -하는 아이디어까지는 생각했지만, 결국 while문을 생각 못해서 끝내 힌트 참고 했다.

 

코드

import sys
n = int(sys.stdin.readline())
num = [int(sys.stdin.readline().strip()) for _ in range(n)]

stack = []
op = []
num_idx = 0

for i in range(1, n+1):
    stack.append(i) # 1부터 오름차순으로 스택에 추가
    op.append('+')
    
    # 스택 맨 위(마지막 append(push))와 입력 수열의 앞과 같으면
    while stack and stack[-1] == num[num_idx]:
        stack.pop() # 뺀다
        op.append('-')
        num_idx += 1 # 꺼낼 때 마다 +1
        
    if num_idx == n: # 입력 수열을 전부 꺼내는데 성공 했으면
        break        # 끝
    
if num_idx != n: # 수열의 모든 숫자를 꺼내지 못했다면 
    print("NO")  # 입력 수열을 만들 수 없다는 뜻 
else:
    for i in op: # 출력
        print(i)

예를 들어, 입력 수열이 [3, 1, 2, 4] 라고 해보자.

for문에서 i=2까지는 while문 조건이 만족되지 않기 때문에 +만 하다가,
i=3일 때, while문 조건을 만족해서 3이 -가 되고 num_idx는 1이 된다. (여기까지 +,+,+,-)

i=4일 때, 스택에 4가 추가(+) 되고 당연히 while 루프는 실행되지 않는다.
i가 4까지 전부 진행됐으므로 for문은 종료된다.

스택에서 수를 꺼낼 때 마다 num_idx가 1씩 증가하고 모두 꺼냈다면 n과 같다는 것인데,
이 예시에서는, num_idx가 1이고 n은 4이기 때문에 수열을 만들 수 없다는 얘기이다.
그러므로 No가 출력된다.

말을 잘 못한 거 같아서 아래에 단계별로 정리하면,

• 입력 : n = 4, num = [3, 1, 2, 4]
• for문 시작
  • i = 1
    stack.append(1) / stack = [1]
    op.append('+') / op = ['+']
    while : stack[-1] == num[num_idx] (1==3) 거짓. while 루프 안 돔
  • i = 2
    stack.append(2) / stack = [1, 2]
    op.append('+') / op = ['+', '+']
    while : stack[-1] == num[num_idx] (2==3) 거짓. while 루프 안 돔
  • i = 3
    stack.append(3) / stack = [1, 2, 3]
    op.append('+') / op = ['+', '+', '+']
    while : stack[-1] == num[num_idx] (3==3) 참.
         - stack.pop() : stack = [1, 2]
         - op.append('-') : op = ['+', '+', '+', '-']
         - num_idx += 1 // num_idx = 1
  • i = 4
    stack.append(4) / stack = [1, 2, 4]
    op.append('+') / op = ['+', '+', '+', '-', '+']
    while : stack[-1] == num[num_idx] (4==1) 거짓. while 루프 안 돔
• 반복문 종료
• num_idx != n 조건 확인 : 1 != 4 참.
  
  • "NO" 출력