[Java] 빈도수 세기

N개의 정수가 차례로 입력으로 주어진다.

각 입력에 대하여 아래와 같은 형식으로 입력 결과를 출력한다.

C F형식으로 세 정수를 출력한다.
C는 현재까지 입력 된 숫자의 종류의 수이다.
F는 이 번에 입력된 숫자가 등장한 횟수이다.

예를 들어서 차례대로 {5, 3, 5, 3, 2}가 입력으로 주어진 경우 출력 결과는 차례로 {1 1, 2 1, 2 2, 2 2, 3 1}가 된다.

입력 형식

첫 줄에는 차례로 입력으로 주어질 정수들의 총 개수를 나타내는 20만이하의 자연수 N이 주어진다. 이후 총 N줄에 걸쳐서 한 줄에 하나 씩 입력이 주어진다.

고려해야 할 순서대로 입력이 주어진다.
모든 숫자는 32비트 정수형임이 보장된다.

출력 형식

각 N개의 숫자에 대한 처리 결과를 한 줄마다 출력한다.

현재까지 입력으로 주어진 숫자의 종류와, 해당 숫자가 등장한 횟수를 공백으로 구분하여 한 줄에 출력한다.

2. 알고리즘 접근

배열을 이용해 빈도수를 세면 될거 같지만 입력형식에 모든 숫자는 32비트 정수형이라는 큰 값이 들어가기에 배열의 인덱스로 사용할 수 없다 -> Map 자료구조 이용

C를 구하는 방법은 Map에 들어있는지 확인 후 없으면 Map에 추가하는 방식을 사용하면 Map의 크기자체가 C값이 된다.

F를 구하는 방법은 Map에 key : value의 형태로 빈도수를 갱신해주면 구할 수 있다

3. 소스코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.TreeMap;

public class Q5J {
    public static final Scanner sc = new Scanner(System.in);
    public static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        int n = sc.nextInt(); // n개의 정수 입력

        // 각 <정수, 빈도수> 형태로 key-value를 저장할 Map 자료구조
        TreeMap<Integer, Integer> frequencyMap = new TreeMap<>();

        for(int i = 0; i < n; i++){
            int x = sc.nextInt(); // 실제 데이터가 들어온다

            // 한번도 등장하지 않은 숫자라면
            if(frequencyMap.containsKey(x) == false){
                // 빈도수를 0으로 초기화
                frequencyMap.put(x, 0);
            }

            // 현재 frequencyMap에 저장된 적 있는 숫자의 개수 저장
            int c = frequencyMap.size();

            // x에 대한 빈도수를 갱신하여 저장
            int f = frequencyMap.get(x) + 1;
            frequencyMap.put(x, f);

            writer.write(String.format("%d %d\n", c, f));
        }

        // C F 형식으로 정수 출력
        // C : 현재까지 입력된 숫자의 종류의 수 ex) 1, 2, 2, 1, 3 -> 1, 2, 2, 2, 3 -> 자료구조에 있는지 확인하고 없으면 빈도수 증가
        // F : 이번에 입력된 숫자가 등장한 수 ex) 1, 2, 2, 1, 3 -> 1, 1, 2, 2, 1 -> 자료구조에 있는지 확인해서 있으면 빈도수 증가
        writer.flush();
        writer.close();
    }
}