[Baekjoon] 17299번: 오등큰수 - Java

https://www.acmicpc.net/problem/17299

17299번: 오등큰수

문제 설명

오른쪽에 있는 숫자 중 자신보다 수열에서 많이 등장한 가장 가까운 수를 찾으면 된다. 문제 자체는 이해하면 어렵지 않지만 구현에서 고생했다.

풀이 방법 1. 이중 반복문(시간 초과)

처음에는 반복문을 통해 순회하면서 해결하려고 했다. 하지만 시간 초과가 발생했다.

for (int i = 0; i < N; i++) {
    int curElem = elems[i];

    boolean isAppearence = false;

    for (int j = i + 1; j < N; j++) {
        int comparison = elems[j];

        if (countsOfAppearence[curElem] < countsOfAppearence[comparison]) {
            isAppearence = true;
            answers[i] = comparison;
            break;
        }
    }
    if (!isAppearence)
        answers[i] = -1;
}

비교 대상을 고정해놓고 오른쪽을 모두 찾아가려고 했던 것이 문제였다. 이 경우 왼쪽부터 시작하여 오등큰수가 나올 때까지 반복한다.

풀이 방법 2. 스택 활용(통과)

혼자 많이 고민해봤지만 해결 방법이 떠오르지 않아 다른 해설 글들을 찾아보고 나서 스택을 활용해 해결하였다. 이 경우 현재 요소가 좌측의 오등큰수인지만 비교하므로 단순 반복보다 훨씬 효율적이다.

for (int i = 0; i < N; i++) {
    while (!stack.empty()
            && countsOfAppearence[elems[i]] > countsOfAppearence[elems[stack.peek()]]) {
                answers[stack.pop()] = elems[i];
    }
    stack.push(i);
}

while (!stack.empty()) {
    answers[stack.pop()] = -1;
}

이 방법의 간략한 알고리즘은 다음과 같다.

1. 오등큰수가 발견될 때까지 인덱스를 스택에 저장해둔다.
2. 오등큰수가 발견된다면 더 많이 발견된 수가 나올 때까지 저장해놓은 인덱스를 pop한 후 오등큰수를 저장한다.

백준 예제로 설명하면 다음과 같다. 

1. A1(i=0) = 1이고 등장 횟수는 3이다. 첫 수이므로 인덱스를 넣고 끝난다.
2. A2(i=1) = 1이고 등장 횟수는 3이다. 오등큰수가 아니므로 인덱스를 넣고 끝난다.
3. A3(i=2) = 2이고 등장 횟수는 2이다. 1의 오등큰수가 아니므로 인덱스를 넣고 끝난다.
4. A4(i=3) = 3이고 등장 횟수는 1이다. 2의 오등큰수가 아니므로 인덱스를 넣고 끝난다.
5. A5(i=4) = 4이고 등장 횟수는 1이다. 3의 오등큰수가 아니므로 인덱스를 넣고 끝난다.
6. A6(i=5) = 2이고 등장 횟수는 2이다.
   1. 2는 4의 오등큰수이므로 A[4]에 2를 넣는다.
   2. 2는 3의 오등큰수이므로 A[3]에 2를 넣는다.
   3. 2는 2의 오등큰수가 아니므로 인덱스 5를 넣고 끝난다.
7. A7(i=6) = 1이고 등장 횟수는 3이다.
   1. 1은 2의 오등큰수이므로 A[5]에 1을 넣는다.
   2. 1은 2의 오등큰수이므로 A[2]에 1을 넣는다.
   3. 1은 1의 오등큰수가 아니므로 인덱스 6을 넣고 끝난다.
8. 입력받은 수열의 오등큰수를 모두 구했다. 현재 스택에 남아있는 인덱스에 해당하는 수는 오등큰수가 없음을 의미한다. 따라서 스택이 빌 때까지 해당 인덱스에 -1을 넣는다.

전체 코드는 다음과 같다.

package baekjoon.stack;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Stack;

public class BOJ17299 {

    public static void main(String[] args) throws Exception {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {

            int N = Integer.parseInt(br.readLine());
            int MAX = 1_000_000 + 1;
            int[] countsOfAppearence = new int[MAX];
            int[] elems = new int[N];
            int[] answers = new int[N];
            Stack<Integer> stack = new Stack<>();

            String[] tokens = br.readLine().split(" ");

            for (int i = 0; i < N; i++) {
                elems[i] = Integer.parseInt(tokens[i]);
                countsOfAppearence[elems[i]]++;
            }

            for (int i = 0; i < N; i++) {
                while (!stack.empty()
                        && countsOfAppearence[elems[i]] > countsOfAppearence[elems[stack.peek()]]) {
                    answers[stack.pop()] = elems[i];
                }
                stack.push(i);
            }

            while (!stack.empty()) {
                answers[stack.pop()] = -1;
            }

            Arrays.stream(answers).forEach((answer) -> wrap(() -> bw.write(answer + " ")));

            bw.flush();
        }
    }

    @FunctionalInterface
    public interface ExceptionConsumer {
        void accept() throws Exception;
    }

    public static void wrap(ExceptionConsumer target) {
        try {
            target.accept();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}