JArchive 프로그래밍 일기

문제

오큰수 백준 17298번

리뷰

단순하게 이중for문으로 풀었을 때 시간초과났다.

직전 수와 그동안 만났던 값들 중의 최대값을 저장해 볼까 하면서 풀었을 땐 틀렸다.

결국 다른 분들의 해설을 찾아봤다.

스택을 이용한 풀이다.

크기가 N인 A배열에는 주어진 수열을 저장한다.

크기가 N인 v벡터는 -1로 초기화 해둔다. 답으로 반환할 수열을 저장한다.

v벡터에는 A의 '인덱스'를 저장한다.

int N;
int A[MAX_LEN+1];    

stack<int> st;
vector<int> v(N, -1); // 반환할 수열  

for(int i = 0; i < N; i++){
    scanf("%d", &A[i]);
}

A[0] 에서는 while문 조건을 불만족하니까. 0을 스택에 push 한다.

오큰수를 찾지 못한 수의 ''인덱스''가 stack st에 쌓여가는 것이다.

스택st 의 top에 있는 인덱스의 A 값이 현재값(A[i]) 보다 작으면, 현재값이 A[ st.top() ]의 오큰수다.

그래서 top 값을 v벡터에 값을 넣어준다.

for(int i = 0; i < N; i++){

    while(!st.empty() && A[st.top()] < A[i]){
        v[st.top()] = A[i];
        st.pop();
    }

    st.push(i);
}

A[ st.top() ]의 오큰수를 찾아줬으니 pop() 한다.

혼자 해봤을 때 안풀려서 약올랐던(?)문제다.

코드

#include <iostream>
#include <stack>
#include <vector>
#define MAX_LEN 1000000
using namespace std;

int N;
int A[MAX_LEN+1];

int main(void){

    freopen("input.txt", "rt", stdin);

    cin >> N ;

    stack<int> st;
    vector<int> v(N, -1); // 반환할 수열  

    for(int i = 0; i < N; i++){
        scanf("%d", &A[i]);
    }

    for(int i = 0; i < N; i++){

        while(!st.empty() && A[st.top()] < A[i]){
            v[st.top()] = A[i];
            st.pop();
        }

        st.push(i);
    }

    for(int i = 0; i < N; i++){
        printf("%d ", v[i]);
    }    

    return 0;

}