오큰수

주어지는 수열의 길이가 1,000,000 입니다. 따라서, 이 문제는 O(NlgN) 혹은 O(n)으로 해결해야 하는 문제입니다.

오큰수 NEG(i)란 수열 S가 주어지고, i < j 인 index가 있을 때 S[i] < S[j]를 만족하는 가장 최솟값 j의 S[j]를 뜻합니다. 즉, 오른쪽에 있는 수 중에서 자기보다 큰 가장 첫번째 숫자를 뜻합니다.

따라서 저는 자연스럽게 뒤에서부터 문제를 접근하였습니다. 간단히 생각해 봤을 때, S[i]가 S[i+1]보다 작으면 S[i]의 오큰수는 S[i+1]이 되기 때문이죠.

그렇다면 문제는 S[i]가 S[i+1]보다 클 때 입니다. 이 경우, S[i+2]부터 쭉 탐색을 해봐야 합니다. 하지만 단순히 이렇게 모두 탐색해버리게 되면 O(n^2)이 될 확률이 높으므로 TLE가 될 수 있습니다.

그러면 다른 방법을 생각해봐야 하는데, 가장 먼저 드는 생각은 NGE(i+1)을 확인하는 것입니다. 만약 이 값이 S[i]보다 크다면, NGE(i)는 NGE(i+1)가 될 것입니다.

저는 단순히 여기까지만 생각하고, 경우를 이렇게 나눴습니다.

if S[i] < S[i+1]:
  NGE(i) = S[i+1]
  
else if S[i] < NGE(i+1):
  NGE(i) = NGE(i+1)
  
else
  NGE(i) = -1

이 코드의 문제점은 NGE(i+1)에 해당하는 S[k]가 있을 때, S[k+n]에 S[i]보다 큰 값이 존재할 수도 있다는 것입니다. 즉,

[10, 3, 5, 20] 이 있을 때, 정답은 [20, 5, 20, -1] 일 것입니다. 하지만 위의 코드 결과는 [-1, 5, 20, -1]이 됩니다. 지금 생각해보면 쉽게 찾을 수 있는 오류인데, 맨 처음 풀 때에는 이 생각이 나질 않았네요.

그래서 그 다음으로 생각한 것은, 그렇다면 지금까지 탐색한 숫자들 중 큰 숫자들에 대한 정보를 가지고 있어야 겠다는 생각이었습니다. 생각해보면, S[i]가 S[i+1]보다 크다면 S[i+2] 이후의 숫자들 중에서 S[i]보다 큰 숫자가 있으면 되는 것인데, 저는 뒤에서부터 앞으로 탐색을 하기 때문에 이 정보들을 갖고 있을 수 있겠다는 생각이 들었습니다.

단순히 탐색한 모든 숫자 정보를 갖고 있으면 그냥 S[i+2]부터 순차적으로 탐색하는 것과 별반 다르지 않기 때문에, 어떻게 갖고 있을까 고민을 하다가 도달한 결론이

• S[i] < S[i+1]이면 S[i+1]를 스택에 넣는다.
• S[i] >= S[i+1]이면, 갖고 있는 스택에서 S[i]보다 큰 수가 나올 때까지 찾는다.
  • 스택 맨 위의 값이 S[i]보다 크면, NGE(i)로 해당 값을 기록하고, 스택에 S[i]를 추가한다.
  • 스택 맨 위의 값이 S[i]보다 작으면, 해당 값을 pop하고 위의 과정을 반복한다.
• 스택이 비어있으면 -1을 기록하고 S[i]를 넣는다.

이런식의 접근을 하면, 스택에 큰 숫자들의 정보가 기록되어 있을 것이고 S[i]를 확인할 때마다 가장 가까운 큰 수를 찾을 수 있습니다.

정답

package bj.tier.gold4;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class BJ17298 {
    public static void main(String[] args) throws Throwable {
        final BufferedReader br = new BufferedReader(
                new InputStreamReader(System.in), 1<<10
        );

        final BufferedWriter bw = new BufferedWriter(
                new OutputStreamWriter(System.out), 1<<10
        );

        final int N = Integer.parseInt(br.readLine());

        final int[] arr = new int[N];

        final StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int ni = 0; ni < N; ni++) {
            arr[ni] = Integer.parseInt(st.nextToken());
        }

        // 큰 숫자들을 오름차순으로 갖고 있는 데크
        final Deque<Integer> deq = new ArrayDeque<>(N+1);
        deq.push(arr[N-1]);

        // 정답 배열(역순)
        final List<Integer> reversedAnswer = new ArrayList<>(N+1);
        reversedAnswer.add(-1);

        // 끝에서 왼쪽으로 탐색
        out:
        for (int ni = N-2; ni >= 0; ni--) {
            if (arr[ni] < arr[ni+1]) {
                reversedAnswer.add(arr[ni+1]);
                deq.push(arr[ni+1]);
                continue;
            }

            while (!deq.isEmpty()) {
                final int value = deq.pop();

                if (arr[ni] < value) {
                    reversedAnswer.add(value);
                    deq.push(value);
                    continue out;
                }
            }

            reversedAnswer.add(-1);
            deq.push(arr[ni]);
        }

        for (int ni = N-1; ni >= 0; ni--) {
            bw.write(Integer.toString(reversedAnswer.get(ni)));
            bw.write(' ');
        }

        bw.flush();
        bw.close();
        br.close();
    }
}