[BOJ 17298] 오큰수 C++/Kotlin

 

17298번: 오큰수

 

 

문제풀이

 

 

오큰수 (Nearest Greater Element)

Next Greater Element - GeeksforGeeks

 

오큰수란 자신의 오른쪽에 있으면서 자기 자신보다 큰 수 중에서 가장 왼쪽에 있는 수를 말한다.

그러한 수가 없는 경우에는 오큰수는 -1이다.

 

 

오큰수는 스택을 사용하여 찾을 수 있다.

예를 보면서 그 과정을 한 번 살펴보자.

 

 

A = [3, 5, 2, 7]인 수열이 있다.

 

 

오큰수를 저장할 배열 NGE를 모두 -1로 초기화하고 스택에는 수열 A의 마지막 원소를 넣어준다.

마지막 원소는 오른쪽에 수가 없으므로 오큰수는 -1이다.

따라서 오른쪽에서 두 번째 원소, A[n - 2]부터 오큰수를 찾는다.

 

 

스택의 top과 현재 원소를 비교했을 때 스택의 top이 더 클 경우에는 NGE 배열에 스택의 top을 저장하고 종료한다.

현재 원소가 스택의 top보다 더 크거나 같다면 스택의 top이 더 클 때까지 pop한다.

만약 스택이 비었다면 오큰수가 없다는 의미이므로 NGE는 -1이다.

이 과정이 끝나면 현재 원소를 스택에 넣어준다.

 

 

현재 원소가 스택의 top인 7보다 작기 때문에 NGE[3] = 7이 된다.

스택에 2를 넣고 다음 원소로 넘어간다. 

 

 

 

2가 현재 원소인 5보다 작기 때문에 pop 해준다.

자신보다 값이 더 큰 7을 만났기 때문에 NGE[2] = 7이고 스택에 5를 넣고 다음 원소로 넘어간다.

 

 

스택의 top인 5가 현재 원소의 값 3보다 크기 때문에 NGE[1] = 3이다.

3을 스택에 넣고 더 이상 NGE를 찾을 원소가 없기 때문에 종료한다.

 

 

 

이렇게 첫 번째 원소까지 진행을 하면 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1을 얻을 수 있다.

 

 

코드

 

C++ 코드

 

 

Kotlin 코드