크기가 N인 수열 $A = A_1, A_2, ..., A_N$이 있다. 수열의 각 원소 $A_i$에 대해서 오큰수 NGE(i)를 구하려고 한다. $A_i$의 오큰수는 오른쪽에 있으면서 $A_i$보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.
예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 $A_1, A_2, ..., A_N$ (1 ≤ $A_i$ ≤ 1,000,000)이 주어진다.
출력 총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
📝 문제 접근 방법
문제 분석
주어진 수열의 각 원소에 대해 오른쪽에 있는 자신보다 큰 수 중 가장 왼쪽에 위치한 수(오큰수)를 찾는 문제입니다.
핵심 아이디어: 스택에 인덱스를 저장하며 배열을 왼쪽에서 오른쪽으로 탐색합니다.
스택을 활용하는 이유
배열을 왼쪽에서 오른쪽으로 탐색하면서 각 원소의 오른쪽에 있는 오큰수를 찾아야 합니다.
단순히 이중 반복문으로 모든 원소를 비교할 경우 시간 복잡도가 $O(N)$이 되므로 비효율적입니다.
스택을 사용하면 각 원소를 한 번씩만 처리하면서 필요한 정보를 추적할 수 있어 시간 복잡도를 $O(N)$으로 줄일 수 있습니다.
인덱스를 저장하는 이유
인덱스를 저장하면 나중에 정확한 위치에 오큰수를 기록할 수 있습니다.
스택에 값을 직접 저장하면 원래 위치를 알기 어려워 결과 배열에 오큰수를 배치하는 과정이 복잡해질 수 있습니다.
인덱스를 저장하면 스택에서 인덱스를 꺼내어 해당 위치에 오큰수를 빠르게 갱신할 수 있습니다.
풀이 전략
결과 배열 초기화
오큰수를 저장할 배열 result를 초기값 -1로 설정합니다. 이렇게 하면 오른쪽에 자신보다 큰 수가 없는 경우 자동으로 -1이 출력됩니다.
스택에 인덱스를 저장
스택에는 원소 값이 아닌 인덱스를 저장합니다. 인덱스를 저장하면 나중에 특정 인덱스의 오큰수를 result 배열에 쉽게 기록할 수 있습니다.
스택에는 오큰수가 아직 결정되지 않은 원소들의 인덱스를 저장해 둡니다. 배열을 오른쪽으로 탐색하면서 현재 원소가 스택에 저장된 인덱스의 원소보다 클 경우 해당 인덱스의 원소의 오큰수를 현재 원소로 지정하고 스택에서 해당 인덱스를 제거합니다.
왼쪽에서 오른쪽으로 탐색
배열을 왼쪽에서 오른쪽으로 순차적으로 탐색하면서 각 원소에 대한 오큰수를 결정합니다.
현재 인덱스의 원소가 스택의 맨 위 인덱스에 해당하는 원소보다 크다면 스택에서 해당 인덱스를 꺼내어 그 인덱스 위치에 현재 원소를 오큰수로 설정합니다.
이 과정을 스택이 비거나 스택의 맨 위 원소가 현재 원소보다 클 때까지 반복합니다.
현재 인덱스를 스택에 추가
모든 비교가 끝나면 현재 인덱스를 스택에 추가하여 이후 원소와 비교할 오큰수 후보로 저장합니다.
예제: $A = [3, 5, 2, 7]$
👩💻 나의 답안
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
result = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
index = stack.pop()
result[index] = arr[i]
stack.append(i)
print(*result)
✨ 새로 알게 된 점
인덱스를 스택에 저장하는 방식
특정 위치에 값을 기록해야 하는 경우 스택에 원소 값이 아닌 인덱스를 저장하는 방식이 유용하다는 것을 알게되었습니다. 탐색 도중 오큰수가 결정될 때 해당 인덱스에 바로 값을 기록할 수 있어 추가적인 위치 추적 작업이 필요하지 않습니다. 배열에 동일한 값이 여러 번 나타날 때에도 인덱스를 저장하면 위치별로 고유하게 다룰 수 있어 각 위치에 정확한 오큰수를 지정할 수 있습니다. 스택에서 인덱스를 꺼낼 때마다 해당 위치의 오큰수를 결정할 수 있으므로 각 인덱스가 처리되는 순서와 결과 배열에 반영되는 순서가 명확해집니다.
