(코딩테스트) 백준 17298번 - 오큰수(Stack)

1) 문제 

 

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

 

예제 입력 1

4
3 5 2 7

예제 출력 1 

5 7 7 -1

 

2) 풀이

2.1)  입력조건

- 완전탐색으로 가면 1백만^2으로 시간복잡도 초과(1억 or 1천만 미만 불만족)

2.2)  풀이과정 

- 다른 방법이 생각 안나서 이중for문으로(시간 초과 나는거 아는데) 풀이 시도

2.3)  코드(시간초과)

#include <bits/stdc++.h>
using namespace std;

int a[1000001],n;

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    
    for (int i = 0; i < n; i++){
        int ret = 0;
        for (int j = i+1; j < n; j++){
            
            if (a[i] < a[j]){
                cout << a[j] << " ";
                ret = 1;
                break;
            }
        }
        if (ret == 0) cout << -1 << " ";
    }
    return 0;
}

3) 해설

3.1)  조건

- 최대 탐색 범위는 100만 * 100만 시간복잡도 불만족 가능성 있음.

- stack을 통해 n번의 탐색만으로 해결

3.2)  사용된 알고리즘

- stack을 사용하여 짝짓기

- index를 stack에 push하여 인덱스를 통해 크기비교 

- stack의 top을 확인 할 때는 항상 스택 사이즈 먼저 확인필요

while (stk.size() && a[stk.top()] < a[i]){
            ret[stk.top()] = a[i];
            stk.pop();
        }
stk.push(i);

 

 

3.3)  완성된 코드

- ret배열을 -1로 초기화하여 ret가 변경 안될 경우 -1 출력

- index를 stack에 push하여 index를 통한 배열의 크기 비교 

#include <bits/stdc++.h>
using namespace std;

int a[1000004],ret[1000004],n;
stack<int> stk;

int main(){
    memset(ret,-1,sizeof(ret));
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        while (stk.size() && a[stk.top()] < a[i]){
            ret[stk.top()] = a[i];
            stk.pop();
        }
        stk.push(i);
    }

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