[알고리즘 / 백준] 1302 - 베스트셀러

 

문제는 위와 같으며 책을 입력 받아 제목을 키로 하고 해당 책이 팔린 횟수를 값으로 하는 딕셔너리를 생성한 뒤, 먼저 횟수를 기준으로 정렬하고 횟수가 같으면 제목을 사전 순으로 정렬하여 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다. 여기서는 기본적으로 제공되는 sorted 함수를 이용하여 문제를 해결하였는데 이 방식 말고 먼저 최대 값을 구한 뒤, 딕셔너리에서 값이 최대 값과 같은 키의 리스트를 생성하고 그 리스트를 정렬하는 방식으로도 문제를 해결할 수 있습니다.

from sys import stdin

n = int(stdin.readline())

books = dict()
for _ in range(n):
    book = stdin.readline().strip()

    if book in books:  # 같은 이름의 책이 이미 팔린 경우 value 증가
        books[book] += 1
    else:              # 처음 책이 팔린 경우 1 증가
        books[book] = 1

# books.items 는 (key, value) 타입의 튜플 리스트를 반환하고 
# 먼저 value(b[1]) 을 내림차순으로 정렬한 뒤, key(b[0]) 을 오름차순으로 정렬
result = sorted(books.items(), key=lambda b: (-b[1], b[0]))
print(result[0][0]) # 가장 앞에 있는 튜플의 키를 출력

 

자바 코드는 다음과 같습니다.

import jdk.dynalink.linker.ConversionComparator;

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

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

        int n = Integer.parseInt(br.readLine());
        Map<String, Integer> books = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String book = br.readLine();

            if (books.containsKey(book)) {
                books.put(book, books.get(book) + 1);
            } else {
                books.put(book, 1);
            }
        }

        List<Map.Entry<String, Integer>> entryList =  new ArrayList<>(books.entrySet());
        Collections.sort(entryList, (o1, o2) -> {
            if (o1.getValue().compareTo(o2.getValue()) == 0) { // 값이 같은 경우
                return o1.getKey().compareTo(o2.getKey());  // 키를 기준으로 오름차순 정렬
            } else {
                return o2.getValue().compareTo(o1.getValue()); // 값을 기준으로 내림차순 정렬
            }
        });

        System.out.println(entryList.get(0).getKey()); // 가장 앞에 있는 값의 키를 출력

    }
}