[인프런] 학급 회장(해쉬)

난이도

• Easy

문제 설명

학급 회장을 뽑는데 후보로 기호 A, B, C, D, E 후보가 등록을 했습니다. 투표용지에는 반 학생들이 자기가 선택한 후보의 기호(알파벳)가 쓰여져 있으며 선생님은 그 기호를 발표하고 있습니다. 선생님의 발표가 끝난 후 어떤 기호의 후보가 학급 회장이 되었는지 출력하는 프로그램을 작성하세요.

입력 형식

• 정수, 문자열

출력 형식

• 문자열

예제 입력 및 출력

**예제 1:**
입력: 15 BACBACCACCBDEDE
출력: C

접근 방법

• 해시맵 사용: 각 후보와 후보에 따른 투표수를 저장하기 위한 해시 맵 사용
• map 순환 : 맵을 loop 하면서 최대 투표자 수 확인

  시간 및 공간 복잡도

• 시간 복잡도: O(n) - 투표 문자열을 한 번 순회 ( O(n))
• 공간 복잡도 : O(1) - 해시맵에 저장되는 요소는 최대 5개(A, B, C, D, E)로 고정되어 있으므로 입력 크기와 상관없이 상수 공간을 사용

코드 구현

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String vote = sc.nextLine();
        Map<Character, Integer> voteMap = new HashMap<>();
        for (char c : vote.toCharArray()) {
            if (voteMap.containsKey(c)) {
                int count = voteMap.get(c);
                voteMap.put(c, count + 1);
            } else {
                voteMap.put(c, 1);
            }
        }
        int max = 0;
        char answer = 0;
        for (char key : voteMap.keySet()) {
            if (voteMap.get(key) > max) {
                max = voteMap.get(key);
                answer = key;
            }
        }
        System.out.println(Character.toString(answer));
    }
}