[JAVA] boj 1302 베스트셀러

문제 링크 : https://www.acmicpc.net/problem/1302

1302번: 베스트셀러

문제

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

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

입력

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

출력

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

예제 입력 1

5
top
top
top
top
kimtop

예제 출력 1

top

예제 입력 2

9
table
chair
table
table
lamp
door
lamp
table
chair

예제 출력 2

table

예제 입력 3

6
a
a
a
b
b
b

예제 출력 3

a

문제 풀이

HashMap을 이용하여 문제를 해결하였다.

 

먼저 책 목록을 모두 입력받고 문제에서 가장 많이 팔린 책이 여러개인 경우 사전 순으로 앞선 책 제목을 출력하라고 하여 sort해주었다.

그 후 배열을 돌면서 책의 제목을 key값 책의 개수를 value로 구성한 HashMap에 동일한 키값이 존재하는 경우 value를 하나씩 올려주면서 저장하였다. 저장하면서 가장 많은 책의 개수를 max에 담아주고 max값보다 현재 입력중인 책의 개수가 크다면 이름을 ans에 담아 주었다.

코드

import java.io.*;
import java.util.*;

public class Main_BJ_1302_베스트셀러 {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int N;
    int max = 0;
    String ans = null;
    
    N = Integer.parseInt(br.readLine());
    String [] books = new String[N];
    for (int i = 0 ; i < N ; i++) {
      books[i] = br.readLine();
    }
    
    Arrays.sort(books);
    
    HashMap<String, Integer> map = new HashMap<String, Integer>();
    
    for (int i = 0 ; i < N ; i++) {
      if (map.containsKey(books[i])) {
        map.replace(books[i], map.get(books[i]), map.get(books[i])+1);
      } else {
        map.put(books[i], 1);
      }
      if (max < map.get(books[i])) {
        max = map.get(books[i]);
        ans = books[i];
      }
    }
    
    System.out.println(ans);
  }
}