[BOJ 17298] 오큰수

17298번: 오큰수

 

1. 문제 설명

 

2. 구현 아이디어 1 - 틀렸습니다, 시간 초과

무식하게 풀 경우 최대 연산 횟수는 1,000,000 + 999,999 + ... + 1 = 500,000,500,000으로 5000억번 가량이 되므로 다른 방법을 찾아야 한다.

 

요즘 코테 공부하면서 큰돌 선생님 강의를 듣고 있는데 문제를 접근할 때 완전탐색 > DP > 그리디 순서로 생각해보라고 했다.

 

완전탐색이 안되기 때문에 DP로 문제를 풀어보려고 했다.

dp[i]에 i번째 원소의 오큰수를 담는다고 했을 때, dp[i-1]이 arr[i]보다 크다면 arr[i]보다 오른쪽에 있으면서 큰 수라고 생각하여 해당 조건을 충족하지 않을 경우에만 for문으로 오큰수를 구하는 로직을 만들었다.

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }

    vector<int> dp = vector(n, -1);
    // dp 배열의 0번째 원소
    for (int i = 1; i < n; ++i) {
        if  (v[i] > v[0]) {
            dp[0] = v[i];
            break;
        }
    }

    for (int i = 1; i < n; ++i) {
        if (dp[i-1] > v[i]) dp[i] = dp[i-1];
        else {
            for (int j = i+1; j <n ; ++j) {
                if (v[j] > v[i]) {
                    dp[i] = v[j];
                    break;
                }
            }
        }
    }

    for (int elem : dp) {
        cout << elem << " ";
    }
    cout << "\n";

    return 0;
}

 

 

7
4 3 2 1 2 3 4

 

위와 같은 상황에서 NGE(2)와 NGE(3) 모두 4가 된다.

NGE(2)를 구할 때 2와 dp[3] (=4)를 비교하기 때문에 만약 dp[i-1]이 현재 원소보다 크다면 오큰수가 제대로 구해지지 않는 것이다.

 

if (v[i-1] < v[i] && dp[i-1] > v[i]) dp[i] = dp[i-1];

 

v[i-1] < v[i]라는 조건을 추가해도 보았지만, 이럴 경우 if문을 충족하는 경우가 매우 적기 때문에 완전탐색이나 다름 없는 코드가 되어 시간 초과가 나왔다.

 

2. 구현 아이디어 3 - 맞았습니다!!

큰돌 선생님의 강의를 참고하여 스택으로 문제를 풀 수 있었다 ...

[3, 2, 1, 4]라는 배열을 생각했을 때 NGE(0)을 구할 때, 2와 비교하면 skip ... 1과 비교하면 skip ... 하다가 4를 만나 NGE(0)=4로 결정된다.

이것이 마치 스택에서 top과 들어올 원소를 비교하여 조건을 만족하면 pop을 하는 과정과 비슷하다!

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v; // 입력값이 저장된 벡터
stack<int> s;
vector<int> ret; // i번째 원소의 오큰수를 저장

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    ret = vector(n, -1); // 오큰수가 없을 경우 -1이기 때문에 -1로 초기화

    for (int i = 0; i < n; ++i) {
        int temp;
        cin >> temp;
        v.push_back(temp);
        while (s.size() && v[s.top()] < v[i]) {
            ret[s.top()] = v[i];
            s.pop();
        }
        s.push(i); // 인덱스를 스택에 넣는다
    }

    for (int i = 0; i < n; ++i) {
        cout << ret[i] << " ";
    }
    return 0;
}

 

i=3일 때를 예시로 들면, stack과 배열들의 상황은 아래 그림과 같다.

현재 s.top()은 v[2]=1이다.

v[2]와 v[3]을 비교했을 때, v[3]이 4로 더 크기 때문에 ret[2] = NGE(2) = 4가 되는 것이다.

 

i=2일 때 오큰수를 구했으니, 스택에서 pop이 되고 3이 스택에 들어간다.

 

이러한 과정을 i=0부터 n-1일 때까지 반복하면 모든 원소에 대한 오큰수를 구할 수 있게 된다.