[백준] S4 1302번 베스트셀러 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

1302번: 베스트셀러

[문제] 

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

[입력]

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

[출력]

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

 

 

---

[풀이]

1. 해시맵(HashMap<key, value>)을 사용한다.

2. 해시맵의 key값으로는 책의 제목을 입력받아 준다.

3. 해시맵의 value값은 책의 이름이 들어올 때마다 1씩 증가를 시켜준다.

4. 전체 입력을 다 받고 나면 value값이 가장 큰 것을 찾아준다.

5. value가 같은 경우, key를 문자열 비교를 통해 사전 순으로 앞에 오는 것을 사용한다.

[접근]

1. 책의 제목에 해당하는 값이 들어오고 해당 값에 따른 개수를 알아야 한다.

2. 각각의 배열을 만들기는 너무 번거롭고, 서로 묶어서 관리할 수 있는 HashMap을 사용한다.

3. HashMap에 입력된 값들을 돌면서 value값이 가장 큰 것을 찾아준다.

4. value가 같은 경우라면 문제에서 사전 순으로 가장 빨리 오는 것을 출력하라고 했으니 문자열 비교를 해 가장 작은 것을 출력해주면 된다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

public class Main_S4_1302_김재욱 {
	static int n;
	static HashMap<String, Integer> map;
	static int size; // 정답의 개수
	static String result = ""; // 정답 문자열

	public static void main(String[] args) throws Exception {
		BufferedReader br = new  BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		size = 0;
		map = new HashMap<>();
		
		for (int i = 0; i < n; i++) {
			String str = br.readLine();
			
			// 이미 있는 단어라면
			if (map.containsKey(str))
				// 해당 단어의 값을 1 증가
				map.put(str, map.get(str) + 1);
			else // 없다면
				// 새로 만들어서 1로 담는다.
				map.put(str, 1);
		}
		
		// 가장 많이 나온 것 찾기
		for (String key : map.keySet()) {
			if (size < map.get(key)) { // 현재 결과의 개수보다 많으면
				size = map.get(key); // 개수를 변경
				result = key; // 정답을 변경
			}
			else if (size == map.get(key)) { // 현재 결과의 개수와 같다면
				if (result.compareTo(key) > 0) // 문자열 비교를 통해
					result = key; // 사전순으로 더 빠른 경우 변경
			}
		}
		
		// 결과 출력
		System.out.println(result);
	}
}