[Java] 시장 추천하기

1. 문제 설명

n명의 시장이 있다
n개의 투표용지와 이름이 주어졌을 때, 가장 많은 투표를 받은 이름을 출력하시오
다만, 많은 투표를 받은 사람이 여러명일 수 있다.

입력 형식

첫 줄에는 투표용지의 수를 나타내는 10만이하의 자연수 N이 주어진다.

이후 총 N줄에 걸쳐서 한 줄에 하나씩 해당 투표용지에 적힌 후보자의 이름이 주어진다.

후보자의 이름은 1~10글자의 알파벳 대문자로 구성된 문자열이다.
두 후보가 같은 이름을 가지는 경우는 없다.

출력 형식

첫 줄에는 가장 많은 표를 획득한 후보자의 표수를 출력한다.

두 번째 줄에는 해당 표수만큼 표를 획득한 후보들의 이름을 공백으로 구분하여 사전순-오름차순으로 출력한다.

2. 알고리즘 접근

문자열을 기준으로 삼을 때는 Map을 사용한다

구현을 위해 필요한 것

• 한 번 이상 등장한 후보의 이름

• 최대 득표 수

  한번 이상 등장한 후보의 이름은 hashMap에 넣어서 관리하고
  최대 득표수는 value값을 기준으로 정렬하여 출력하기에 treeMap을 사용한다

3. 소스코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Q5K {
    static final Scanner sc = new Scanner(System.in);
    static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {

        int n = sc.nextInt(); // 투표 수

        Map<String , Integer> frequencyMap = new HashMap<>();
        Set<String> winnersList = new TreeSet<>();// 사전 순 정렬을 위해 TreeSet

        int maxFrequency = 0; // 가장 많은 득표수

        for(int i = 0; i < n; i++){
            String name = sc.next();

            if(frequencyMap.containsKey(name) == false){
                // 이 이름이 등장한적 있다면 지나간다
                frequencyMap.put(name, 0);
            }

            // 빈도수 갱신
            int freq = frequencyMap.get(name) + 1;
            frequencyMap.put(name, freq);

            // 최대 빈도 계산
            if(freq > maxFrequency){
                maxFrequency = freq;
            }
        }
        // 최대 득표수 출력
        writer.write(String.format("%d\n", maxFrequency));

        // 최대 득표한 동점 후보들 이름을 사전순으로 출력
        for(String name : frequencyMap.keySet()){
            if(frequencyMap.get(name) == maxFrequency){ // 최대 득표자라면
                winnersList.add(name);
            }
        }

        // winnersList = 최다 득표를 한 동점자들(정렬 되어 있다)
        boolean first = true;
        for(String name : winnersList){
            writer.write(name+" ");
        }
        writer.flush();
        writer.close();
    }
}