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

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

17298번: 오큰수

 

접근: 

엘지 코테 당시, 해당 오큰수문제와 거의 비슷하게 출제되었는데

당시 문제를 풀 때는, 인덱스 뽑아서 2중 반복문으로 돌리다보니 ( 시간복잡도 O(N^2) )

테스트케이스는 통과를 했지만, 히든 케이스에서 10^6 x 10^6 = 10^12 에서 분명히 시간초과가 발생했을 것이다.

 

다른 솔루션을 찾아본 결과, 스택으로 (O(N)) 시간초과 없이 해결한 케이스가 있어 이를 참고하였다.

https://cocoon1787.tistory.com/347

[C/C++] 백준 17298번 - 오큰수 (스택)

 

소스 코드:

#include <iostream>
#include <stack>

using namespace std;
int N;
stack<int> s;
int ans[1000001];
int seq[1000001];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> N;
  // 수열 입력받기
  for (int i=0; i<N; i++){
    cin >> seq[i];
  }

  ///////
  for(int i=N-1; i>=0; i--){
    while (!s.empty() && s.top() <= seq[i]){
      s.pop();
    }

    if (s.empty()){ // 오큰수가 없으면
      ans[i] = -1;
    }
    else{
        ans[i]= s.top();
    }
    s.push(seq[i]);
  }
  ///////
  

  // 정답 출력
  for (int i=0; i<N; i++){
    cout << ans[i] << " ";
  }
  
  
}