BOJ - 오큰수(17298)

골드4 : stack 문제이다.

풀이

아, 정말 아쉬운 문제였다. 하지만 배운 것이 있었다. Stack을 기본적으로 사용하는 이유은 어떤 복잡도 문제를 해결하기 위함이다. 이 부분은 뒤에 다시 살펴보도록 하자. 일단 이 문제를 단순하게 순회해서 푼다면 최악의 경우 $O(n^2)$가 걸리기 때문에 n=1,000,000인 상황에서 바로 시간초과가 난다. 그래서 이를 n에 가까운 속도로 풀어야 한다.

그렇다면 문제를 분석해보자. 오큰수는 현재 값에서 오른쪽에 있는 큰값들 중 가장 첫번째로 나오는 녀석이라고 정j의할 수 있다. 그렇기 때문에, 만약 현재값이 4인데, 다음 값이 10이면 그 10이 오큰수가 될 수 있겠다. 여기서 알 수 있는 점은 아, 큰놈이 나오면 그 전값은 이 큰놈이 오큰수가 될 가능성이 있구나. 정도이다. 그럼 이런 상황은 어떨끼?

4 3 9

이런 상황에서 4의 입장에서 3은 오큰수가 아니다. 하지만 3의 입장에서 9는 오큰수이다. 그렇다면 4의 오큰수는? 9이다. 여기서, 현재 값보다 미래 값이 큰 경우 과거값들 중에 미래 값을 오큰수로 가지는 녀석이 있을 수 있다는 결론을 내릴 수 있다.

1 7  9 7 8  3 1  4 10  3 10
7 9 10 8 10 4 4 10 -1 10 -1

자 그럼, 어떤 분기에서 이 가정이 틀릴 수 있을까? 일단 미래 값이 현재값과 같다면, 현재 값의 오큰수는 그 미래값이 아니다. 여기서 stack을 사용해보자. stack에는 다음에 나올 미래값에 의해 오큰수가 결정될 후보 위치를 말한다. 좀 어려우니 적어보자.

11
1 7  9 7 8  3 1  4 10  3 10

index : 0
value : 1
stack 현재 상태
0 

index : 1
value : 7
stack top (position): 0
value : 1
    오큰수 후보 발견, 답안 업데이트
    stack before
    0 
    answer before
    0 0 0 0 0 0 0 0 0 0 0 
    stack after
    
    answer after
    7 0 0 0 0 0 0 0 0 0 0 
stack 현재 상태
1 

index : 2
value : 9
stack top (position): 1
value : 7
    오큰수 후보 발견, 답안 업데이트
    stack before
    1 
    answer before
    7 0 0 0 0 0 0 0 0 0 0 
    stack after
    
    answer after
    7 9 0 0 0 0 0 0 0 0 0 
stack 현재 상태
2 

index : 3
value : 7
stack top (position): 2
value : 9
stack 현재 상태
2 3 

index : 4
value : 8
stack top (position): 3
value : 7
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 3 
    answer before
    7 9 0 0 0 0 0 0 0 0 0 
    stack after
    2 
    answer after
    7 9 0 8 0 0 0 0 0 0 0 
stack 현재 상태
2 4 

index : 5
value : 3
stack top (position): 4
value : 8
stack 현재 상태
2 4 5 

index : 6
value : 1
stack top (position): 5
value : 3
stack 현재 상태
2 4 5 6 

index : 7
value : 4
stack top (position): 6
value : 1
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 4 5 6 
    answer before
    7 9 0 8 0 0 0 0 0 0 0 
    stack after
    2 4 5 
    answer after
    7 9 0 8 0 0 4 0 0 0 0 
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 4 5 
    answer before
    7 9 0 8 0 0 4 0 0 0 0 
    stack after
    2 4 
    answer after
    7 9 0 8 0 4 4 0 0 0 0 
stack 현재 상태
2 4 7 

index : 8
value : 10
stack top (position): 7
value : 4
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 4 7 
    answer before
    7 9 0 8 0 4 4 0 0 0 0 
    stack after
    2 4 
    answer after
    7 9 0 8 0 4 4 10 0 0 0 
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 4 
    answer before
    7 9 0 8 0 4 4 10 0 0 0 
    stack after
    2 
    answer after
    7 9 0 8 10 4 4 10 0 0 0 
    오큰수 후보 발견, 답안 업데이트
    stack before
    2 
    answer before
    7 9 0 8 10 4 4 10 0 0 0 
    stack after
    
    answer after
    7 9 10 8 10 4 4 10 0 0 0 
stack 현재 상태
8 

index : 9
value : 3
stack top (position): 8
value : 10
stack 현재 상태
8 9 

index : 10
value : 10
stack top (position): 9
value : 3
    오큰수 후보 발견, 답안 업데이트
    stack before
    8 9 
    answer before
    7 9 10 8 10 4 4 10 0 0 0 
    stack after
    8 
    answer after
    7 9 10 8 10 4 4 10 0 10 0 
stack 현재 상태
8 10 

7 9 10 8 10 4 4 10 -1 10 -1

순서대로 따라가다 보면 이해가 될 것이다. 최종적으로 stack에 남는 값은, 맨 마지막 값까지 보았는대도 오큰수를 찾을 수 없었던, 인덱스 들이다. 오큰수를 찾지 못한 녀석들을 마지막으로 -1로 업데이트하면 끝난다.

Code

//
//  main.cpp
//  algorithm_prac
//
//  Created by 최완식 on 2021/04/05.
//
 
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// stack에 위치 정보를 넣으면 중복 연산을 줄일 수 있다..!!!!
int N;
int a[1000001] = {0,};
int v[1000001] = {0,};
vector<int> s;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    for (int i = 0; i < N; i++) {
        cout << "index : " << i << '\n';
        cout << "value : " << a[i] << '\n';
        
        if (!s.empty()) {
            cout << "stack top (position): " << s.back() << '\n';
            cout << "value : " << a[s.back()] << '\n';
        }
        
        while (!s.empty() && a[s.back()] < a[i]) {
            cout << "    오큰수 후보 발견, 답안 업데이트" << '\n';
            cout << "    stack before" << '\n' << "    ";
            for (int j = 0; j < s.size(); j++) {
                cout << s[j] << " ";
            }cout << '\n';
            cout << "    answer before" << '\n' << "    ";
            for (int j = 0; j < N; j++) {
                cout << v[j] << " ";
            }cout << '\n';
            
            v[s.back()] = a[i];
            s.pop_back();
            
            cout << "    stack after" << '\n' << "    ";
            for (int j = 0; j < s.size(); j++) {
                cout << s[j] << " ";
            }cout << '\n';
            cout << "    answer after" << '\n' << "    ";
            for (int j = 0; j < N; j++) {
                cout << v[j] << " ";
            }cout << '\n';
        }
        s.push_back(i);
        cout << "stack 현재 상태" << '\n';
        for (int j = 0; j < s.size(); j++) {
            cout << s[j] << " ";
        }cout << '\n' << '\n';
        
    }
    
    while (!s.empty()) {
        v[s.back()] = -1;
        s.pop_back();
    }
    
    for (int i = 0; i < N; i++) {
        cout << v[i] << " ";
    }
 
    return 0;
}
 

Reference

• 백준(17298번) - 오큰수