[BaekJoon] 17299 오등큰수 (Java)

1.  문제 링크

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

2.  문제

요약

• 크기가 N인 수열 A = $A_1, A_2, ..., A_N$이 있고 수열의 각 원소 $A_i$에 대해 오등큰수 NGF(i)를 구하려고 합니다.
• $A_i$가 수열 A에서 등장한 횟수를 F($A_i$)라고 했을 때, $A_i$의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F($A_i$)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미합니다.
• 그러한 수가 없는 경우에는 오등큰수는 -1입니다.
• 수열 A가 주어졌을 때, 각 원소 $A_i$의 오등큰수 NGF(i)를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 크기 N이 주어지고 두 번째 줄에 1보다 크거나 같고 1,000,000보다 작거나 같은 수열 A의 원소 $A_1, A_2, ..., A_N$가 주어집니다.
• 출력: 첫 번째 줄에 총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static final int MAX = 1000000;
    static StringBuilder sb = new StringBuilder();
    static int N;
    static int[] num, counting;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        num = new int[N];
        counting = new int[MAX + 1];
        for(int idx = 0; idx < N; idx++) {
            num[idx] = scanner.nextInt();
            counting[num[idx]]++;
        }
    }

    static void solution() {
        Stack<Integer> stack = new Stack<>();
        for(int idx = 0; idx < N; idx++) {
            while(!stack.isEmpty() && counting[num[stack.peek()]] < counting[num[idx]]) {
                num[stack.pop()] = num[idx];
            }
            stack.push(idx);
        }
        while(!stack.isEmpty()) {
            num[stack.pop()] = -1;
        }
        for(int idx = 0; idx < N; idx++) sb.append(num[idx] + " ");
        System.out.println(sb);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 수열 A의 각 원소들을 입력받아 num이라는 1차원 배열에 넣어주는데, 이 때 각 수들의 등장 횟수를 세서 counting이라는 1차원 배열에 저장합니다.
• 수열 A의 원소들을 첫 원소부터 마지막 원소까지의 index를 Stack을 생성하여 Stack에 넣는데 Stack에 넣는 과정에서 오등큰수를 구합니다.
  • 원소를 Stack에 넣기 전에 Stack이 비어있지 않고 현재 Stack에 넣으려는 수의 등장 횟수보다 Stack에서 뽑은 수의 등장 횟수가 적은지 확인합니다.
  • 만약 위 조건이 만족된다면, Stack에서 뽑은 수의 오등큰수는 현재 Stack에 넣으려는 수가 됩니다.
    • 위 조건을 반대로 생각하면 Stack에 수를 넣을 때, Stack에서 뽑은 수의 등장 횟수가 현재 Stack에 넣으려는 수의 등장 횟수보다 크거나 같을 때에 넣는데, 그럼 Stack에 있는 수들은 등장 횟수에 대해 내림차순으로 정렬되어 있다고 볼 수 있습니다. 그렇기 때문에 새로 들어오는 수의 등장 횟수가 Stack에서 뽑은 수의 등장 횟수보다 크다면 이 수는 Stack에서 뽑은 수의 오른쪽에 위치하는 등장 횟수가 더 큰 수 중 가장 왼쪽에 위치하는 수가 됩니다.
  • 모든 원소에 대해 위 작업을 진행합니다.
• 아직 Stack에 남아있는 index들이 있다면, 해당 수들은 오등큰수가 없는 것이기 때문에 해당 수들의 오등큰수는 -1이 됩니다.