17298 오큰수

일단 비교를 해야하니 담아둘 컨테이너가 필요하다.

배열을 백만개 선언할 수 도있고,

벡터를 이용할 수도 있지만,

간단하게 배열을 써보자.

그렇게 한다면, 최악의 경우 (제일 큰 숫자가 맨 오른쪽에 있는 경우)

탐색시간이 O(백만^2) 이 들어서 시간초과가 날 것이다.

 

 

스택에 하나씩 넣고 빼면서 비교해볼까

4

3 5 2 7

을 예로들면,

stack 3

stack 3 5

들어간 5가 3보다 크므로 출력

stack 3 5 2

stack 3 5 2 7

들어간 7이 5보다 크므로 출력

들어간 7이 2보다 크므로 출력

7 다음에 들어간 것이 없으므로 -1 출력

 

 

.... 흠 무언가 의미가 다가오지 않는다. 이럴 때는 발상을 뒤집어 보자.

 

 

배열에 3 5 2 7을 넣어놓고,

stack에 배열 끝 자리부터 거꾸로 담는다.

그전에 비교 대상을 넣어주기 위해 inf를 먼저 담는다. (inf = 1e7+10 로 설정)

stack inf

 

stack inf

스택 top이 7보다 크므로,

스택의 top을 answer[7의 index=3]에 저장한다.

하지만 top이 inf이면 -1을 저장한다.

그 후 7을 스택에 넣는다.

 

stack inf 7

스택 top이 2보다 크므로,

스택의 top(7)을 answer[2의 index=2]에 저장한다.

그 후 2를 스택에 넣는다.

 

stack inf 7 2

스택 top이 원소 5보다 작다! ("2")

과감히 pop한다. 작은 것이 없을 때까지.

즉, 오른쪽에 있는 숫자 중에서 큰 수중 가장 왼쪽에 있는 것(가장 최근을 고르고 있는 중인것이다!

 

stack inf 7

스택 top이 원소 5보다 크다.

스택의 top(7)을 answer[5의 인덱스=1]에 저장한다.

그 후 5를 스택에 넣는다.

 

stack inf 7 5

스택 top이 원소 3보다 크다.

스택의 top(5)을 answer[3의 인덱스=0]에 저장한다.

이렇게 for문을 다 돌았으면, answer를 순서대로 출력한다.

 

 

#include <cstdio>
#include <stack>
using namespace std;
stack<int> s;
int a[1000000];
int ans[1000000];

int main() {
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; i++){
        scanf("%d", &a[i]);
    }
    s.push(1e7+1);
    for (int i=n-1; i>=0; i--){
        while(s.top() <= a[i]) s.pop();
        if (s.top() > 1e7) ans[i] = -1;
        else ans[i] = s.top();
        s.push(a[i]);
    }
    for (int i=0; i<n; i++){
        printf("%d ", ans[i]);
    }
    return 0;
}