[class2]백준 1874번(스택 수열) - 코딩테스트 23일차(2025.02.13)

문제유형

스택

풀이 방법 도출 과정

1. 스택의 연산을 활용하여 1~n까지의 수에 대해서 주어진 순서대로 만드는 것이 목표

2. 만약  4, 3, 6, 8, 7, 5, 2, 1의 수열을 만든다고 할 때 다음과 같이 하면된다.

1234 ++++
123 - 
12 -
1256 ++
125 -
12578 ++
1257 -
123 -
12 -
1 -
-

이런 방식으로 만들면 된다.

3. 하지만 NO가 되는 경우는 이렇다. 만약 1, 2, 5, 3, 4인 경우

1 +
-
2 +
-
345 +++
34 -
????

34가 필요한데 43으로 밖에 꺼내지 못하므로 이런 경우는 NO라고 하는 것이다.

4. 이러한 점을 보았을 때, 스택에 넣을 게 없을 때 NO라고 하는 듯하다.

5. 이점을 이용해서 코드를 작성해보도록 하겠다.

시간 복잡도

입력 처리: O(N)

whlie문: O(N)

최종 시간 복잡도 O(N)

 

나머지의 시간 복잡도는 O(1)이기에 계산하지 않음

코드 및 간단설명

스택을 활용하여 풀었다. 

import sys

n = int(sys.stdin.readline().strip())
stack, ans = [], []
find = True
now = 1

for _ in range(n):
    num = int(sys.stdin.readline().strip())
    
    while now <= num:
        stack.append(now)
        ans.append("+")
        now += 1

    if stack and stack[-1] == num:
        stack.pop()
        ans.append("-")
    else:
        find = False
        break  # 더 이상 검사할 필요 없음

if not find:
    print("NO")
else:
    print("\n".join(ans))