백준 17299 - Java

 

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

public class ODKS {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        //N갯수 입력
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] ngf = new int[N];
        int[] freq = new int[1000001]; // 등장 횟수 저장 배열 (Ai의 범위가 1 <= Ai <= 1,000,000)
        Stack<Integer> stack = new Stack<>();

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(input[i]);
            freq[arr[i]]++; // 각 숫자의 등장 횟수 기록
        }

        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && freq[arr[stack.peek()]] < freq[arr[i]]) {
                ngf[stack.pop()] = arr[i]; // 오등큰수 설정
            }
            stack.push(i); // 인덱스를 스택에 넣음
        }
        while (!stack.isEmpty()) {
            ngf[stack.pop()] = -1;
        }
        //출력
        for (int i = 0; i < N; i++) {
            sb.append(ngf[i]).append(" ");
        }

        System.out.println(sb.toString().trim());
    }
}

 

freq[arr[i]]++; // 각 숫자의 등장 횟수 기록
여기에서 막혔었다. 이걸 생각하지 못해서 chatGPT에 물어본 결과

코드 freq[arr[i]]++

이 부분은 arr[i]에 해당하는 숫자가 등장할 때마다 그 숫자의 등장 횟수를 하나씩 증가시키는 역할을 합니다. 이때 freq 배열의 인덱스는 수열의 값 arr[i]가 되고, 그 값의 위치에 있는 등장 횟수를 증가시킵니다.

과정 설명:

1. arr[i]: 수열 A의 i번째 숫자입니다.
2. freq[arr[i]]: 배열 freq에서 arr[i]에 해당하는 인덱스에 있는 값은 그 숫자가 지금까지 등장한 횟수입니다.
3. ++: 현재까지 등장한 횟수에 1을 더해 그 숫자의 등장 횟수를 증가시킵니다.

예시:

만약 수열이 arr = [1, 1, 2, 3, 4, 2, 1]로 주어졌을 때, freq 배열이 다음과 같이 갱신됩니다:

• 처음에는 freq 배열이 모두 0으로 초기화되어 있습니다.
• i = 0 (첫 번째 원소):
  • arr[0]은 1이므로, freq[1]++을 실행합니다.
  • freq[1]의 값이 1로 증가합니다.
• i = 1 (두 번째 원소):
  • arr[1]도 1이므로, 다시 freq[1]++을 실행합니다.
  • freq[1]의 값이 2로 증가합니다.
• i = 2 (세 번째 원소):
  • arr[2]는 2이므로, freq[2]++을 실행합니다.
  • freq[2]의 값이 1로 증가합니다.

이 과정이 계속 진행되어 수열에서 숫자가 등장할 때마다 그 숫자의 등장 횟수가 기록됩니다.

최종적으로 freq 배열은 다음과 같은 값을 가집니다:

• freq[1] = 3 (숫자 1은 3번 등장)
• freq[2] = 2 (숫자 2는 2번 등장)
• freq[3] = 1 (숫자 3은 1번 등장)
• freq[4] = 1 (숫자 4는 1번 등장)

이 정보를 바탕으로 오등큰수(NGF)를 구할 때 등장 횟수를 비교하게 됩니다.

 

라고 설명해주었다. 

 

생각해보니 이것은 결국 counting sort (계수 정렬)이다.