백준 - 1302 - 베스트셀러

HashMap 을 사용하여 알고리즘 문제를 푸는데 모르는 부분이 있어 정리하고자 한다.

 

 

https://www.acmicpc.net/problem/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 가 같은 경우라면 문제에서 사전 순으로 가장 빨리 오는 것을 출력하라고 했으니 문자열 비교를 해서 가장 작은 것을 출력해주면 된다.

 

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

public class B_1302 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int size = 0; // 정답의 개수
        String result = ""; // 정답 문자열

        HashMap<String, Integer> map = new HashMap<>();

        for(int i = 0 ; i < N; i++){
            String str = br.readLine();
			
            // 이미 있는 단어라면 해당 단어의 값을 1 증가
            if(map.containsKey(str)){
                map.put(str, map.get(str) + 1);
            }
            // 없다면 새로 만들어서 1로 담는다.
            else {
                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);
    }
}

 

 

 

 

 

참고 블로그 :
https://blackvill.tistory.com/39