[17299] 오등큰수

🔗 문제 링크

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

❔ 문제 설명

크기가 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 = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 $F(A_3=2) < F(A_7=1)$ 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

총 N개의 수 NGF(1), NGF(2), ..., NGF(N)을 공백으로 구분해 출력한다.

⚠️ 제한사항

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

• 둘째에 수열 A의 원소 $A_1, A_2, ..., A_N (1 ≤ A_i ≤ 1,000,000)$이 주어진다.

---

💡 풀이 (언어 : Java)

어제 풀었던 오큰수의 응용 문제이다. 풀이 기본 틀은 같고 빈도수로 판별하기 때문에 따로 반복문으로 전체 한번 돌아서 빈도수를 기록해주는 배열을 하나 만들어줬다. 그리고 비교할때 스택에 넣은 것은 인덱스를 넣어주고, 숫자배열[스택의 인덱스]를 빈도수 배열의 인덱스로 조회해서 비교해서 스택에서 넣고 빼주는 작업을 반복한다. 마지막까지 스택에 남은 수들은 조건에 만족하지 못하는 수들이므로 -1로 바꿔주고 정답 조건대로 문자열을 만들어서 반환하면 끝이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 입력 받은 숫자들을 int 배열로 변환
        int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Stack<Integer> stack = new Stack<>();
        // 숫자 배열의 빈도수로 만든 배열을 생성
        int[] count = new int[1000001];
        for (int idx : arr)
            count[idx]++;
    
        for (int i = 0; i < n; i++) {
            // 빈도 배열의 값으로 stack에서 제거 여부를 판별
            while (!stack.isEmpty() && count[arr[stack.peek()]] < count[arr[i]]) {
                arr[stack.pop()] = arr[i];
            }
            // 현재 원소가 더 작거나, 스택에 비교할 수가 없으면 현재의 원소를 넣는다
            stack.push(i);
        }
        // 스택에 남아 있는 인덱스는 오큰수가 없는 것들이므로 스택에서 모두 뽑아서 해당 배열 값을 -1로 바꿈
        while (!stack.isEmpty()) {
            arr[stack.pop()] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for (int num : arr) {
            sb.append(num).append(" ");
        }
        System.out.print(sb);
    }
}