문제
김형택은 도서 대여점을 운영하고 있다. 오늘 하루 대여된 책의 이름을 모두 기록하였는데, 가장 많이 대여된 책의 이름을 출력하는 프로그램을 작성하시오. 가장 많이 대여된 책이 여러 권이라면, 사전 순으로 가장 앞서는 책의 이름을 출력한다.
입력
첫째 줄에 오늘 하루 대여한 책의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐 책의 이름이 한 줄에 하나씩 주어진다. 책의 이름은 공백 없이 알파벳 소문자로만 이루어져 있으며, 길이는 최대 50이다.
출력
첫째 줄에 가장 많이 대여된 책의 이름을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 top top top top kimtop | top |
풀이
HashMap으로 각 책의 대여 횟수를 카운팅하고, 최대값을 가진 책들 중 사전 순으로 앞서는 것을 선택한다.
- 입력을 받으면서 HashMap에 각 책 이름의 등장 횟수를 누적한다
- 동시에 현재까지의 최대 대여 횟수(
max)를 갱신한다 - HashMap을 순회하여
max와 같은 횟수를 가진 책 이름들을 List에 모은다 - List를 사전 순으로 정렬(
Collections.sort)하여 첫 번째 원소를 출력한다
핵심 아이디어: 빈도 계산은 HashMap으로 O(1)에 처리하고, 동점 처리는 사전 정렬로 해결한다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Day267BOJ1302베스트셀러 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Map<String, Integer> map = new HashMap<>();
int max = 0;
for (int i = 0; i < n; i++) {
String book = br.readLine();
map.put(book, map.getOrDefault(book, 0) + 1);
max = Math.max(max, map.get(book));
}
List<String> list = new ArrayList<>();
for (Map.Entry<String, Integer> entry : map.entrySet()) {
if (entry.getValue() == max)
list.add(entry.getKey());
}
Collections.sort(list);
System.out.print(list.get(0));
}
}복잡도
- 시간: O(N log N)
- 공간: O(N)