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

문제

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

17298번: 오큰수

문제 해결

스택문제라서 최대한 스택으로 풀어보려 처음에는 선택한 수부터 선택한 수보다 큰 수가 나올 때까지 작은 수들을 스택에 넣은 다음

스택에 있는 수들을 차례대로 꺼내어 꺼낸 수의 인덱스~선택한 수보다 큰수 인덱스 까지 다시 오큰수를 구하는 알고리즘을 구현했는데 38%에서 시간초과가 나서 다른 블로그를 참고해서 풀었다....

 

일단 처음 수를 스택에 넣는다. 그 다음수와 현재 수를 비교했을 때 만약 현재 수가 크다면 다음 수를 스택에 넣는다, 만약 현재 수가 다음수 보다 작으면 현재값의 오큰수는 다음 수가 되고 남아있는 스택에 있는 수들도 비교한다. 

 

사실 내가 처음 짰던 알고리즘과 답과의 차이를 모르겠지만 코드상에서 뭔가 좀 더 비효율적인면이 있었던것 같았다.

 

코드

#include <iostream>
#include <stack>
#include <stdio.h>
#include <cstring>
using namespace std;
int main(void){
    int N,ary[1000002],cnt = 0,j,h;
    int result[1000002];
    memset(result,-1,sizeof(result));
    stack <pair<int,int>> s;
    cin >> N;
    for(int i = 0;i<N;i++){
        scanf("%d",&ary[i]);
    }
    result[N-1] = -1;
    for(int i = 0;i<N-1;i++){
        s.push({ary[i],i});
        if(ary[i+1]>ary[i]){
            result[i] = ary[i+1]; s.pop();
            int temp = s.size();
            for(int j = 1;j<=temp;j++){
                int num = s.top().first;
                if(num>=ary[i+1]){break;}
                else{result[s.top().second] = ary[i+1];s.pop();}
            }
        }
    }
    for(int i = 0;i<N;i++){printf("%d ",result[i]);}
}