[Algorithm] 백준 17298 오큰수 c++

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

17298번: 오큰수

 

풀이

• 수열(a)의 왼쪽부터 인덱스와 스택을 활용해 오큰수 탐색한다.
• 스택에 들어있는 값은 아직 오큰수를 구하지 못하였거나 오큰수가 없는 수의 인덱스이다.

 

세부 풀이

1. 우선 스택에 첫 인덱스인 0을 넣고 다음 인덱스로 넘어간다.
2. 스택에 들어있는 값과 현재 인덱스에 각각 대응하는 값을 비교한다.
3. 현재 인덱스의 값이 더 큰 경우 오큰수를 발견한 것이다. nge에 값을 넣는다.
4. (스택에 들어있는 값이 더 큰 경우 오큰수를 발견하지 못한 것이다.)
5. 스택이 empty할 때까지 2-3번을 반복한다.
6. 현재 인덱스를 스택에 넣고 다음 인덱스로 넘어간다.
7. 수열을 모두 탐색할때까지 2-6번을 반복한다.
8. 7번까지 마치고 스택에 남아있는 값은 오큰수가 없는 값이므로 -1을 넣는다.

세부 풀이 예시

 

소스코드

#include <stack>
using namespace std;

int a[1000001];
int nge[1000001];
stack<int> s;

int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];

    for(int i=0; i<n; i++){
        while(!s.empty() && a[s.top()] < a[i]){
            nge[s.top()] = a[i];
            s.pop();
        }
        s.push(i);
    }

    while(!s.empty()){
        nge[s.top()] = -1;
        s.pop();
    }

    for(int i=0; i<n; i++) cout<<nge[i]<<" ";

    return 0;
}