[백준] No.17298 - 오큰수 (C++, 스택)

문제

 

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

풀이

 

solved.ac 난이도: Gold 4

 

스택 자료구조로 해결 가능한 문제.

 

수열의 뒤에서부터 차례대로 진행하면 해결할 수 있다.

수열의 크기가 arr_size라 할 때 수열(arr)의 가장 마지막 수는 오큰수를 가질 수 없으므로 nge(arr_size-1)= -1을 저장하고

스택에 해당 수, arr[arr_size-1]를 넣고 시작하자.

 

 

stack<int> st;
nge[arr_size-1] = -1;
st.push(arr[arr_size -1]);
 
for(int i = arr_size-2; i>=0  ; --i){
  while(!st.empty() && st.top() <= arr[i])
    st.pop();
 
  if(st.empty())
    nge[i] = -1;
  else
    nge[i] = st.top();
    
  st.push(arr[i]);
}

 

arr_size-2인 수부터 역방향으로 진행한다.

 

현재의 수(arr[i])가 스택의 top보다 크거나 같다면

스택의 top은 arr[i]의 오큰수가 될 수 없다. 따라서 스택의 top에서 해당 수를 pop을 해준다.

이 과정을 스택의 top에 arr[i]보다 큰 수가 나타나거나 스택이 빌 때까지 반복해준다.

 

while문을 빠져나온 경우는 2가지가 존재한다.

1. 스택의 top에 arr[i]보다 큰 수가 나타난 경우

 해당 수가 arr [i]로부터 오른쪽에서 가장 가까운 큰 수이다.

 

2. 스택이 비어있는 경우

 arr[i]보다 큰 수가 오른쪽에 없으므로 nge[i] = -1 이다.

 

이후 스택에 arr[i]를 push해준다.

만약 while문에서 스택이 모두 비어 버려도 arr[i]는 스택에 담긴 수들 보다 큰 수 이므로 스택에 push되면 

스택에서 제거된 수들은 신경 쓸 필요가 없다.

또한, 가장 작은 수가 push되더라도 다음 수가 스택에서 그 수를 pop하므로 오큰수의 대상에서 제외된다. 

 

 

예를 들어 8 2 3 5 9의 수열을 생각해보자.

 

8 2 3 5 9    => 가장 끝 수는 오큰수가 없다. 

              -1        stack: 9

 

8 2 3 5 9   => stack.top 보다 작다. nge(5) = stack.top = 9

           9 -1       stack: 9 5

 

8 2 3 5 9  => stack.top 보다 작다. nge(3) = stack.top = 5

       5  9 -1       stack: 9 5 3

 

8 2 3 5 9  => stack.top 보다 작다. nge(2) = stack.top = 3

   3 5  9 -1      stack: 9 5 3 2

 

8 2 3 5 9  => stack.top 보다 크다. stack.top > 8 일때 까지 pop해준다. 

9 3 5  9 -1     stack: 9 5 3 2 ->...->  9 ,  nge(8) = stack.top = 9

   

                  

코드