[백준] 17298번 오큰수 - Python / 알고리즘 기초 1/2 - 자료구조 1 (연습)

ByungJik_Oh·2025년 3월 19일

[Baekjoon Online Judge]

목록 보기

11/244

💡 문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -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의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

💭 접근

먼저 오큰수의 정의를 이해해보자.
오큰수(NGE) : list a의 원소 a[i]의 오큰수를 구하기 위해선 a[i]보다 오른쪽에 있는 (i값이 큰) 원소 중 처음으로 a[i]보다 큰 수를 말한다.
이를 구하기 위해선,

우선 stack에 0~n-1의 index를 차례대로 append한다.
각 과정에서, stack의 가장 마지막 인덱스를 가지는 a 원소가(a[stack[-1]])이 방금 입력된 i번째 a 원소(a[i])보다 작다면 nge의 stack[-1]번째 원소에 a[i]를 저장(nge[stack.pop()] = a[i])해준다.

ex) 예제
i = 0 (a[0] = 3), stack = [] (stack[-1] = None)
-> stack.append(0)
i = 1 (a[1] = 5), stack = [0] (stack[-1] = a[0] = 3)
-> a[1] > a[stack[-1]], nge[stack.pop()] = a[1]
...

이때, 오큰수를 찾지 못한 index들이 stack에 저장되어 있으므로 stack.pop()을 통해 stack의 마지막부터 원소를 꺼내어 a[i]보다 큰 수가 나올때까지 반복해준다.
for 문이 끝난 후에도 stack에 남아있는 index들은 오큰수가 없는 것이므로 nge를 -1 초기화해주면 신경쓰지 않아도 된다.

📒 코드

n = int(input())
a = list(map(int, input().split()))
stack = [] # a 원소의 index를 저장하기 위한 stack
nge = [-1] * n # -1로 초기화

for i in range(n):
	# while문을 통해 stack의 끝부터 원소를 하나씩 꺼내며 비교
    while stack and a[stack[-1]] < a[i]:
        nge[stack.pop()] = a[i]
    stack.append(i) # 반복이 끝난 후 i번째 index append

print(*nge)