[BOJ / C++] 17298번 : 오큰수

문제

크기가 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)을 공백으로 구분해 출력한다.

Solved.ac 레벨

골드 IV

풀이

스택을 활용하여 입력받은 숫자 배열을 뒤에서부터 판단하였다.

arr[] = {3, 5, 2, 7}

 

1. arr[3] = 7

 

7

<stack>

top()

7

<ans>

-1

 

i = 3의 7을 판단할 때 이 이후에는 수가 없으므로 처음에는 스택이 비어있는 상태다. 따라서 7의 오큰수는 없다. 

오큰수가 없으므로 정답을 담을 배열의 3번째 원소에 -1을 저장한다.

그 후 7을 스택에 집어넣는다.

 

2. arr[2] = 2

 

2

<stack>

top()

2

7

<ans>

7

-1

 

현재 스택에는 7이 들어가있고, st.top() 또한 7이다. 하지만 이는 arr[2] = 2보다 크므로 스택의 요소를 꺼내지 않고, ans 배열에 st.top()인 arr[2]의 인덱스 위치, ans[2]에 7을 저장한 후 2를 스택에 담는다.

 

3. arr[1] = 5

 

5

<stack>

top()

5

7

<ans>

7

7

-1

 

현재 스택에는 2, 7이 들어가있으며 st.top()은 2다. 현재 원소인 arr[1]의 5보다 st.top()이 작거나 같고, 스택이 비어있지 않으므로 st.top()이 현재 탐색 중인 원소보다 크거나 같을 때까지 스택의 요소를 pop한다. 따라서 2가 스택에서 나온다.

 

그 후 다시 st.top()은 7이 되고 이는 5보다 크므로 ans 배열에 7을 인덱스에 맞게 저장한 뒤 5를 스택에 push한다.

 

4. arr[0] = 3

 

3

<stack>

top()

5

7

<ans>

5

7

7

-1

 

현재 스택에는 5, 7이 들어가있으며 st.top()은 5다. 현재 원소인 arr[0]의 3보다 크므로 ans 배열에 5을 저장한다.

 

그 후 ans를 출력해주면 정답이 된다.

 

Code

#include<bits/stdc++.h>

using namespace std;

int n;
int arr[1000001];
int ans[1000001];
stack<int> st;

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

    cin >> n;

    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    for(int i = n; i >= 1; i--) {
        while(!st.empty() && st.top() <= arr[i]) {
            st.pop();
        }

        if(st.empty()) {
            ans[i] = -1;
        } else {
            ans[i] = st.top();
        }

        st.push(arr[i]);
    }

    for(int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }

    return 0;
}

17298번: 오큰수