[백준] 17298번 : 오큰수

문제

 

---

풀이

 

이중 for문을 쓰면 아주 쉬운데...시간제한때문에 시간복잡도를 줄여야한다.

 

이 문제를 푸는 아이디어는 오큰수를 구하지 못한 수를 스택에 저장하는 것이다.

더 자세하게 말하자면 오큰수를 구하지 못한 수의 인덱스를 스택에 저장하면 되겠다.

 

오큰수를 구하지 못한 수(A)를 스택에 저장하고, 그 뒤로 입력되는 수(B)에 대해 B가 A의 오큰수가 될 수 있는지 확인한다.

될 수 있다면 배열의 A 인덱스 값을 B로 바꿔준다. 마지막까지 스택에 남아있는 수는 오큰수를 구하지 못한 것이므로 -1로 바꿔준다.

---

소스코드

 

#include <iostream>
#include <stack>

using namespace std;

int num_arr[1000000];

void oaken(int length) {
    stack<int> index; //오큰수를 구하지 못한 수의 index를 저장

    for (int i = 0; i < length; i++) {
        while (!index.empty() && num_arr[i] > num_arr[index.top()]) { //num_arr[i]가 오큰수가 될 수 있는가?
            num_arr[index.top()] = num_arr[i];
            index.pop();
        }
        index.push(i);
    }
    while (!index.empty()) { //여전히 스택에 남아있는 수라면 오큰수가 없는 것
        num_arr[index.top()] = -1;
        index.pop();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> num_arr[i];
    oaken(N);
    for (int i = 0; i < N; i++)
        cout << num_arr[i] << ' ';
}

전체 소스코드다.

 

    for (int i = 0; i < length; i++) {
        while (!index.empty() && num_arr[i] > num_arr[index.top()]) { //num_arr[i]가 오큰수가 될 수 있는가?
            num_arr[index.top()] = num_arr[i];
            index.pop();
        }
        index.push(i);
    }

num_arr[i]에 대해 이 수가 스택 index안에 있는 수보다 큰지, 그니까 오큰수가 될 수 있는지 while 문에서 확인한다.

만약 오큰수가 될 수 있다면 스택에 있던 수를 빼오고 오큰수를 입력해준다.

num_arr[i]는 아직 오큰수를 찾지 못한 수이므로 while문을 빠져나온 뒤 push로 스택에 넣어준다.

 

    while (!index.empty()) { //여전히 스택에 남아있는 수라면 오큰수가 없는 것
        num_arr[index.top()] = -1;
        index.pop();
    }

마지막까지 스택에 남아있는 수는 오큰수가 없는 것이므로 -1을 입력하며 스택에서 빼준다.