https://www.acmicpc.net/problem/1874
백준 1874번 스택수열

문제 파악

1. n (1 ≤ n ≤ 100,000) 이므로 O(N^2)은 안된다.
2. NO를 출력해야 하는 경우 : 현재 구해야할 입력된 수열의 요소보다 실제로 스택에 넣은 자연수의 마지막 요소가 클 경우(e.g. 3을 뽑아야 하는데 자연수 스택의 현재 마지막 요소가 4일 경우)
3. 문제에서의 상황을 그대로 구현하면 되지 않을까

코드

from sys import stdin

input = stdin.readline

n = int(input())
seq = [0 for _ in range(n)]
for i in range(n):
    seq[i] = int(input())
now_v = 1
stack = [1]
ans = ["+"]
for target in seq:
    while True:
        if now_v < target:
            ans.append("+")
            now_v += 1
            stack.append(now_v)
        elif stack[-1] == target:
            ans.append("-")
            stack.pop()
            break
        else:
            print("NO")
            exit()
for i in ans:
    print(i)

now_v : 차곡차곡 쌓여지는 자연수 스택에서 그 다음으로 들어갈 수를 저장하는 변수
stack 과 ans는 1이 들어간 상태에서 시작
입력받은 수열의 요소에 for문으로 접근

• now_v가 현재 수열의 요소인 target보다 작다면 stack에 자연수 추가
• stack의 가장 위(마지막) 요소와 target이 같다면 pop
• 위 경우가 모두 아니라면 NO : 왜냐하면 위 조건들이 다 아니라는 것은 1. target이 이미 stack에 들어가있다. 2. 하지만 target이 stack의 가장 마지막에 있지 않다. 3. 그렇다면 뽑을 수 없다.

TIL

• 조건문을 분기할 때 조건의 기준이 달라져도 되는가?

if now_v < target:
            ...
elif stack[-1] == target:
            ...

위 코드처럼 target과 now_v를 비교하고 그 다음 조건에선 stack[-1]과 비교하는게 좋은 코드인가 모르겠다.

• 책에서는 ans를 문자열로 저장해서 마지막에 출력한다.

ans = ""
...
if ...
	ans += "+\n"
...
print(ans)

하지만 위 방식대로 ans를 처리하면 시간이 몇배로 많이 걸렸다.
문자열로 출력 시 4952ms
똑같은 코드를 단지 ans를 리스트로 하고, 마지막 출력 때 반복문을 통해 출력하면 196ms가 걸렸다.