[BaekJoon] 17298번 - 오큰수 [Java][C++]

문제 링크

---

1. 아이디어

오큰수는 해당 수보다 오른쪽에 위치하면서 해당 수보다 큰 수 중에서 가장 왼쪽에 위치한 수이다. 간단하게는 해당 수를 기준으로 오른쪽으로 한 칸씩 탐색하며 해당 수보다 큰 수가 나오면 이를 출력하는 과정을 반복하면 되지만 수열의 크기가 최대 1,000,000이어서 O(N²)의 시간 복잡도로는 해결할 수 없다.

해당 문제는 역방향 탐색과 단조 스택을 활용해서 해결했는데, 역방향 탐색으로 수를 스택에 담는다면 이 스택은 해당 수의 오른쪽 수 전체를 고려해서 만들어진 스택이 된다. 스택에 수를 담을 때는 해당 수가 스택의 top에 위치한 수보다 크거나 같다면 top에 위치한 수는 해당 수뿐만 아니라 해당 수 왼쪽에 위치한 모든 수에 대해 오큰수가 아니므로 스택에서 제거한다. top에 위치한 수가 해당 수보다 작거나 같은 동안 전부 오큰수가 안되므로 스택에서 제거하는 과정을 반복하고, 만약 스택이 비어있다면 이는 해당 수가 오른쪽에 위치한 모든 수보다 크거나 같은 것이므로 해당 수는 오큰수가 존재하지 않는다. top에 위치한 수가 해당 수보다 크다면 역방향 탐색으로 수를 스택에 삽입하므로 top에 위치한 수가 해당 수보다 큰 수 중 가장 왼쪽에 위치한 수가 되며 이 값이 오큰수가 된다. 오큰수를 구했다면 이를 결과로 저장한 후 해당 수를 스택에 삽입하고 다시 왼쪽 수에 대해 이 과정을 반복하면 된다.

스택에 삽입은 항상 top 보다 작은 수를 삽입하므로 이 스택은 단조 감소 스택이 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[n];

        for (int i = n - 1; i >= 0; i--) {
            int x = arr[i];

            while (!stack.isEmpty() && stack.peek() <= x) {
                stack.pop();
            }

            res[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(x);
        }

        for (int x : res) {
            sb.append(x).append(" ");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

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

int arr[1000000];
int res[1000000];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> arr[i];

    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        int x = arr[i];

        while (!st.empty() && st.top() <= x) {
            st.pop();
        }

        res[i] = st.empty() ? -1 : st.top();
        st.push(x);
    }

    for (int i = 0; i < n; i++) {
        cout << res[i] << ' ';
    }
}

---

3. 디버깅

수열의 각 수에 대해 오큰수를 저장하는 배열이 없어도 되지 않을까 했는데 반례들이 자꾸 나와서 오큰수를 별도로 저장한 후 일괄 출력하는 방식으로 해결했다.

---

4. 참고

없음.

---