섹션 4. HashMap, TreeSet - 1. 학급 회장(해쉬)

📌 문제 설명

학급 회장을 뽑기 위해 학생들이 투표한 결과가 문자열로 주어집니다. 후보는 A, B, C, D, E 중 한 명이며, 투표 결과를 분석하여 가장 많은 표를 얻은 후보(문자)를 출력하세요.

단, 반드시 한 명의 회장이 정해지도록 투표 결과가 주어진다고 가정합니다.

---

📝 입력 & 출력

입력

• 첫 번째 줄: 반 학생 수 N (5 ≤ N ≤ 50)
• 두 번째 줄: 투표 결과 문자열 (길이 N)

출력

• 가장 많은 표를 얻은 후보의 기호 (알파벳 1개)

---

🔸 예제 입력 & 출력

예제 입력 1

15
BACBACCACCBDEDE

 

예제 출력 1

C

---

💡 해결 방법

• HashMap<Character, Integer>를 이용하여 각 후보자의 득표 수를 카운트합니다.
• 문자열을 순회하며 문자의 개수를 맵에 저장하고,
• 최다 득표 수를 가진 후보를 찾아 출력합니다.

---

💻 코드 구현 (Java)

package partHashTree;

import java.util.*;

public class Problem1 {
	public char solution(int n, String s) {
		char result = ' ';
		HashMap<Character, Integer> map = new HashMap<>();
		for(char x : s.toCharArray()) {
			map.put(x, map.getOrDefault(x, 0) + 1);
		}
		int max = Integer.MIN_VALUE;
		for(char key : map.keySet()) {
			if(max < map.get(key)) {
				max = map.get(key);
				result = key;
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Problem1 T = new Problem1();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		String s = kb.next();
		System.out.print(T.solution(n, s));
		kb.close();
	}
}

---

📖 코드 설명

• HashMap을 활용하여 투표 결과를 문자별로 카운트합니다.
• map.getOrDefault(x, 0)은 해당 문자가 없을 경우 0으로 초기화해주는 역할을 합니다.
• max 값을 기준으로 가장 많은 표를 받은 후보를 result에 저장하여 반환합니다.

---

⏳ 시간 복잡도 분석

• 투표 문자열 길이 N에 대해 한 번씩 순회하며 map에 저장 → O(N)
• map의 keySet을 다시 순회하며 최댓값 비교 → O(1) (최대 5명)
• 총 시간 복잡도: O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런