[구현 / BOJ 17298 / C++] 오큰수

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

17298번: 오큰수

 

1) 스택을 만든다.
1-1) 오큰수를 찾으면 저장하고 pop한다.  스택이 빌때까지 시행한다.
1-2) 입력되는 수를 push 한다.

재미있는 문제이다.. NGE(n)이라는 수열의 값을 구하라 했으니깐

즉, x일때 NGE(x)의 값, 함수를 만들면 끝나는 문제다. 근데 이거 그냥 아무생각없이 이중 for문으로 구하면 

시간 초과 난다... 다른 방법을 생각해야한다. (백만 x 백만의 시간복잡도를 가진다)

 

x일때 y의 값이다. 즉 (x,y)와 같이 짝을 지을 수 있을 것이다. 보통 이렇게 짝을 지어야하는 문제는

스택을 사용하면 된다 !! 게다가 문제조건도 방향이 오른쪽으로만 향하니 쉽게 구현할 수 있다.

 

[3, 5, 2, 7] 일 경우를 보자.

 

우선 빈 스택을 만든다.

 

[]

 

3이 들어온다. 빈 스택이므로 push !

 

[3]

 

5가 들어온다. 그런데 5는 3보다 큰수다. 즉, 오큰수가 된다.

그렇다면, 3에 해당하는 y의 값은 5라는 뜻이다. (3,5)와 같이 짝을 지어주고 저장을 하자.

그리고나서, 3은 더이상 쓸모없으니 Pop을 한다.

 

아직 5의 오큰수는 구하지 못했으니, 스택에 5를 push 한다.

 

[5]

 

2가 들어온다. 5보다 작으므로 오큰수도 될 수 없다. 그냥 2를 push 한다.

 

[5, 2]

 

7이 들어온다! 7은 2보다 크다. 즉 오큰수다! (2,7) 짝을 지어주고 2를 pop하자.

 

[5]

 

다시 7을 push하기전에 스택의 top을 확인해보니 5이다. 7은 5보다 크므로 오큰수가 될 수 있다. 

(5, 7) 짝을 짓고 5를 pop하자. 그리고 일관성 있는 규칙을 위해 7을 다시 push !

 

[7]

 

이렇게 되고, 입력된 수들의 짝을 순서대로 하고, (7의 짝은 없다.)

(3, 5), (5, 7) , (2, 7), (7, X)

 

X만 -1로 바꾸고 출력하면 끝!

 

 

#include <bits/stdc++.h>

using namespace std;

int N, tmp, res[1000004];
stack<pair<int,int>> S;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    fill(res, res+1000004, -1);
    
    for(int i = 0 ; i < N ; i++) {
        cin >> tmp;
        
        while(!S.empty() && (S.top().second < tmp)) {res[S.top().first] = tmp; S.pop();}
        S.push({i, tmp});
      
        
    }
    
    for(int i = 0 ; i < N ; i++) cout << res[i] << ' ';
}