백준 17298 오큰수 (stack)

문제 : 17298번: 오큰수 (acmicpc.net)

17298번: 오큰수

 

풀이과정

for문을 2중으로 돌리게 된다면 풀 수 있을것 같은 문제입니다.

하지만 수열의 최대 크기가 1,000,000 이기 때문에 O(N^2)의 시간복잡도로는 시간제한 1초 내에 해결할 수 없습니다.

 

따라서 stack을 사용한다면 O(N) 시간 내에 해결이 가능합니다.

 

간단한 풀이과정을 작성해보면,

수열의 맨 끝 숫자부터 시작해서 해당 숫자보다 더 큰 숫자가 스택에 있는지 탐색하고,

answer 배열에 있다면 저장하고, 없다면 -1을 저장하는 것이 아이디어 입니다.

 

예를들어 v = [3 5 2 7] , stack = [ ] , answer = [ ] 인 상태에서 시작해보겠습니다.

 

-------------------------------------------

1. v의 3번째 원소인 7에 대해서

stack이 비어있기 때문에 answer에도 -1이 저장됩니다.

그리고 stack에 7을 저장합니다.

=>  v = [3 5 2 7] , stack = [7] , answer = [    -1]

-------------------------------------------

2. v의 2번째 원소인 2에 대해서

stack의 top 원소인 7이 2보다 더 크기때문에 answer에는 7이 저장됩니다.

그리고 stack에 2를 저장합니다.

v = [3 5 2 7] , stack = [7 2] , answer = [   7 -1]

-------------------------------------------

3. v의 1번째 원소인 5에 대해서

 

3-1. stack의 top 원소인 2는 5보다 더 작기때문에 pop 해줍니다.

v = [3 5 2 7] , stack = [7] , answer = [   7 -1]

 

3-2. stack의 top 원소인 7이 5보다 더 크기때문에 answer에는 7이 저장됩니다.

그리고 stack에 5를 저장합니다.

v = [3 5 2 7] , stack = [7 5] , answer = [  7 7 -1]

-------------------------------------------

4. v의 0번째 원소인 3에 대해서

stack의 top 원소인 5는 3보다 더 크기때문에 answer에는 5가 저장됩니다.

그리고 stack에 3을 저장합니다.

v = [3 5 2 7] , stack = [7 5 3] , answer = [5 7 7 -1]

 

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int N;
vector < int > v;
stack < int > st;
int answer[1000001];

void solution() {
    for(int i=N-1; i>=0; i--) {
        int now = v[i];
        // stack이 비어있다면 오큰수가 없음
        if(st.empty()) {
            answer[i] = -1;
            st.push(now);
        }
        else {
            while(!st.empty()) {
                if(now < st.top()) {
                    answer[i] = st.top();
                    st.push(now);
                    break;
                }
                else if(now >= st.top()) {
                    st.pop();
                }
            }
            if(st.empty()) {
                answer[i] = -1;
                st.push(now);
            }
        }
    }
}

int main() {
    int num;
    scanf("%d",&N);
    for(int i=0; i<N; i++) {
        scanf("%d",&num);
        v.push_back(num);
    }
    solution();
    for(int i=0; i<N; i++)
        printf("%d ",answer[i]);
}