문제 링크: https://www.acmicpc.net/problem/17298
문제 파악
이 문제는 각 원소의 오큰수 NGE(i) 를 구하는 문제다.
오큰수가 없으면 -1을 출력한다.
오큰수 NGE(i):
i의 오른쪽에 있으면서A[i]보다 큰 수들 중 가장 왼쪽에 있는 수.
예제로 감 잡아보자.
- A =
[3, 5, 2, 7]- NGE(1): 3보다 큰, 오른쪽에서 가장 왼쪽 → 5
- NGE(2): 5보다 큰, 오른쪽에서 가장 왼쪽 → 7
- NGE(3): 2보다 큰, 오른쪽에서 가장 왼쪽 → 7
- NGE(4): 7보다 큰 수 없음 → -1
해결 아이디어 (처음 생각)
어떤 자료구조를 쓰면 좋을까?
NGE(i)는 “오른쪽에서 나보다 큰 수를 가장 먼저 만나는 지점”을 찾는 것.- 단순히 왼쪽→오른쪽으로 훑으면서 매번
val보다 큰 첫 원소를 찾으려 하면
매 i마다 전부 확인해야 해서 시간복잡도O(N^2)가 된다.
처음엔 큐로 이렇게 시도해봤다(아이디어는 맞지만 구현·복잡도 이슈로 부적절):
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
q = deque(map(int, input().strip().split()))
NGE = []
for i in range(N):
val = q[i]
# q에서 popleft() 하며 val보다 큰 값을 찾으면 append하고 break,
# 끝까지 못 찾으면 -1 추가… 라는 접근
while q:
cur = q.popleft()
if cur > val:
NGE.append(cur)
break
else:
NGE.append(-1)
print(*NGE)왜 문제였나?
popleft()할 때마다 원본 q가 계속 바뀜 → 인덱싱/로직 꼬임.- 무엇보다 매 인덱스마다 전부 확인 →
O(N^2)→ 시간초과.
해답 및 풀이 (정석: 스택으로 O(N))
핵심은 “아직 오큰수를 못 찾은 인덱스들” 을 스택에 들고 가는 것.
- 배열을 왼쪽 → 오른쪽으로 한 번 순회.
- 현재 값이 스택 top(=앞에서 쌓아둔 인덱스의 값) 보다 크면,
→ 그 현재 값이 곧 top의 오큰수.
→ 해당 인덱스를pop하고 결과에 기록.
→ 이 과정을 작지 않을 때까지 반복. - 처리 후, 현재 인덱스 i를 스택에 push
(i의 오큰수는 아직 모름 → 나중에 더 큰 값이 나타나면 그때 채워짐) - 순회가 끝나면, 스택에 남은 인덱스들은 끝까지 오큰수가 없었으니 -1 유지.
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
NGE = [-1] * N
stack = [] # 아직 오큰수를 못 찾은 인덱스들을 저장
for i in range(N):
# 현재 값으로 스택 상단(이전 인덱스들)의 오큰수를 해결할 수 있는 동안 pop
while stack and A[stack[-1]] < A[i]:
idx = stack.pop()
NGE[idx] = A[i]
# 현재 인덱스는 아직 오큰수 미정 → 스택에 보류
stack.append(i)
print(*NGE)코드 흐름 시각화
A = [1, 2, 2, 2, 3] 으로 따라가 보자.
초기:
A = [1, 2, 2, 2, 3]
NGE = [-1, -1, -1, -1, -1]
stack = []i = 0, A[0] = 1
- 스택 비어있음 → while 통과
- 현재 인덱스 0 push
stack = [0]
NGE = [-1, -1, -1, -1, -1]i = 1, A[1] = 2
- top = 0, A[0] = 1 < 2 → 0의 오큰수는 2
- pop 0,
NGE[0] = 2 - 현재 인덱스 1 push
stack = [1]
NGE = [2, -1, -1, -1, -1]i = 2, A[2] = 2
- top = 1, A[1] = 2 < 2 ? ❌
- 현재 인덱스 2 push
stack = [1, 2]
NGE = [2, -1, -1, -1, -1]i = 3, A[3] = 2
- top = 2, A[2] = 2 < 2 ? ❌
- 현재 인덱스 3 push
stack = [1, 2, 3]
NGE = [2, -1, -1, -1, -1]i = 4, A[4] = 3
- top = 3, A[3] = 2 < 3 →
NGE[3] = 3, pop 3 - top = 2, A[2] = 2 < 3 →
NGE[2] = 3, pop 2 - top = 1, A[1] = 2 < 3 →
NGE[1] = 3, pop 1 - 더 이상 조건 X → 현재 인덱스 4 push
stack = [4]
NGE = [2, 3, 3, 3, -1]끝. 스택에 남은 4(값 3)는 끝까지 오큰수 없음 → -1 유지.
최종 NGE = [2, 3, 3, 3, -1]
한 줄 정리
- 큐로 전부 탐색하면
O(N^2)이라 시간초과. - 스택에 “오큰수 미해결 인덱스”를 보류해두고, 더 큰 값을 만날 때마다 한 번에 해결하면
O(N)에 끝난다. - 스택에 무엇을 저장할지(값? 인덱스?), 언제 pop할지만 명확히 하면 깔끔하게 풀린다.
스택에 무얼 저장하고, 어떨 때 pop을 하며 풀 수 있을지
다시 한번 잘 생각해봐야겠다.
Frontend Engineers