[Baekjoon/Java] 1302번 베스트셀러

문제

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

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

 

입력

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

 

출력

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

 

문제 풀이

 

 

첫번째 풀이 - 런타임 에러(IndexOutOfBounds)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Map<String, Integer> map = new HashMap<String, Integer>();
		
		int N = sc.nextInt();
		int max = 0;
		for(int i=0; i<N; i++) {
			String book = sc.next();
			
			if(map.containsKey(book)) {
				int tmp = map.getOrDefault(book, 0);
				map.replace(book, tmp+1);
			}else {
				map.put(book, 1);
			}
		}
		
		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.println(list.get(0));
		
	}
}

현재 max는 0으로 초기화되어있다.

만약 예제가 3 a b c 와 같이 주어진다면 map에 book이 포함되어있다는 조건문에 들어가지 않기 때문에 max는 그대로 0이고 list.get(0)을 해주는 부분에서 list는 비어있는데 0번째 인덱스의 값을 출력하라니까 에러가 났다. 다행히도 이 부분은 반례를 빠르게 찾아내서 어렵지 않게 해결한 에러였다.

 

 

최종 풀이

같은 책의 제목이 여러 번 나올 수도 있기 때문에 hashmap을 사용해서 key에는 책 제목을, value에는 책의 빈도 수를 넣어주었다. 그리고 첫번째 풀이에서 만났던 에러를 해결하기 위해 map에 책 제목이 포함되어있던 포함되어있지 않던 value 값으로 max를 구해주도록 했다. 그래야 3 a b c와 같은 예제에서 max 값이 1이 나올 수 있기 때문 !

그리고 list를 하나 생성해서 hashmap의 길이만큼 반복하며 value값이 max인 것들을 list 안에 넣어줬다.

만약 책의 빈도 수가 같다면 사전 순으로 가장 앞선 책의 제목을 출력해야하기 때문에 Collections.sort를 사용하여 사전 순으로 정렬했다. 정렬이 끝났다면 가장 첫번째에는 사전 순에서 가장 빠른 책의 제목이 있을테니 이를 출력하면 된다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Map<String, Integer> map = new HashMap<String, Integer>();
		
		int N = sc.nextInt();
		int max = 0;
		for(int i=0; i<N; i++) {
			String book = sc.next();
			
			if(map.containsKey(book)) {
				int tmp = map.getOrDefault(book, 0);
				map.replace(book, tmp+1);
			}else {
				map.put(book, 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.println(list.get(0));
		
	}
}

 

새롭게 알게 된 점

int tmp = map.getOrDefalut(book, 0);

map 안에 book이라는 key가 있다면 key에 대한 value를 반환하고 없다면 0을 반환한다 !

지금 떠오른건데 그럼 굳이 map에 key가 포함되어있는지에 대한 조건문 없이 위의 코드만 작성해도 될 것 같다.

for(Map.Entry<String, Integer> entry: map.entrySet()){
     if(entry.getValue() == max) list.add(entry.getKey());
}

위 코드에서 Map.Entry 객체 컬렉션이 있는데 이를 통해 한 번의 조작으로 entry.getValue(), entry.getKey()로 키와 값을 한꺼번에 구할 수 있다.

 

느낀점

문자열을 사용하여 푸는 알고리즘은 쉬워보이면서도 어려운 것 같다. 나는 '사전순' 이런 단어만 나오면 지레 겁을 먹곤 한다. 특히 2차원 배열에서 정렬이 여러 개 주어지면 풀기도 전부터 한숨이 나오곤 한다.. 완전 내 코드가 아니라 다른 사람의 풀이를 참고한거라서 이틀 뒤에 다시 풀어봐야겠다 ㅠㅠ

 

https://www.acmicpc.net/problem/1302

1302번: 베스트셀러