문제 설명

오늘 하루 동안 팔린 책의 제목이 주어졌을 때,
가장 많이 팔린 책의 제목을 출력하는 문제이다.

단, 다음 조건을 만족해야 한다.

가장 많이 팔린 책이 여러 개일 경우
→ 사전순으로 가장 앞선 제목 출력

---

입력

첫째 줄

N

책의 개수

조건

1 ≤ N ≤ 1000

다음 줄부터 N개의 책 제목

---

출력

가장 많이 팔린 책의 제목 출력

---

입력 예시

6
a
a
a
b
b
b

출력 예시

a

---

문제 해결 아이디어

이 문제의 핵심은 다음 두 가지이다.

1. 문자열 개수 세기
2. 최대값 + 사전순 처리

즉,

Map or 정렬

을 활용하는 문제이다.

---

내가 작성한 코드

나는 TreeMap을 사용해서
문자열을 자동으로 사전순 정렬하면서 개수를 저장했다.

코드

import java.util.*;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        TreeMap<String, Integer> books = new TreeMap<>();

        for(int i = 0; i < N; i++) {
            String book = sc.next();
            books.put(book, books.getOrDefault(book, 0) + 1 );
        }

        String resultBook = "";
        int max = 0;

        for(String key : books.keySet()) {
            if(max < books.get(key)) {
                resultBook = key;
                max = books.get(key);
            }
        }

        System.out.println(resultBook);
    }
}

---

강의 코드 (정렬 방식)

강의에서는 배열에 저장 후 정렬하여 해결했다.

코드

import java.util.*;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        String[] titles = new String[N];

        for (int i = 0; i < N; i++)
            titles[i] = sc.next();

        Arrays.sort(titles);

        String maxTitle = titles[0];
        int maxCount = 1;
        int currentCount = 1;

        for (int i = 1; i < N; i++) {

            if (!titles[i].equals(titles[i - 1]))
                currentCount = 0;

            currentCount++;

            if (maxCount < currentCount ||
                (maxCount == currentCount && titles[i].compareTo(maxTitle) < 0)) {

                maxCount = currentCount;
                maxTitle = titles[i];
            }
        }

        System.out.println(maxTitle);
    }
}

---

강의 코드 (Map 방식)

강의에서는 HashMap을 사용하는 방식도 제시했다.

코드

import java.util.*;

class Main
{
    public static void main (String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        Map<String, Integer> titles = new HashMap<>();

        for (int i = 0; i < N; i++) {
            String title = sc.next();
            titles.put(title, titles.getOrDefault(title, 0) + 1);
        }

        String maxTitle = "";
        int maxCount = 0;

        for (Map.Entry<String, Integer> title : titles.entrySet()) {

            if (title.getValue() > maxCount ||
                (title.getValue() == maxCount && title.getKey().compareTo(maxTitle) < 0)) {

                maxTitle = title.getKey();
                maxCount = title.getValue();
            }
        }

        System.out.println(maxTitle);
    }
}

---

내 코드 vs 강의 코드 비교

1. 자료구조 선택 차이

내 코드

TreeMap 사용

• 자동으로 사전순 정렬
• 탐색 시 별도 비교 필요 없음

---

강의 코드 (Map)

HashMap 사용

• 정렬 없음
• 비교할 때 직접 사전순 조건 처리

---

강의 코드 (정렬)

배열 + 정렬

• 정렬 후 연속 구간으로 개수 계산

---

2. 사전순 처리 방식

내 코드

TreeMap이 자동 정렬

→ 먼저 나오는 key가 사전순 앞

---

강의 코드

title.getKey().compareTo(maxTitle) < 0

→ 직접 비교

---

핵심 차이

방식	특징
내 코드	TreeMap으로 정렬 자동 처리
강의 코드	HashMap + 비교
강의 코드2	정렬 후 처리

---

3. 시간복잡도 비교

내 코드 (TreeMap)

삽입: O(log N)
전체: O(N log N)

---

강의 코드 (HashMap)

삽입: O(1)
전체: O(N)

---

강의 코드 (정렬)

정렬: O(N log N)

---

4. 어떤 방식이 더 좋은가

내 코드 장점

• 코드 간단
• 사전순 자동 처리

단점

• TreeMap이라 성능이 HashMap보다 느림

---

강의 코드 장점

• HashMap → 빠름
• 명확한 조건 처리

---

핵심 개념

1. 문자열 빈도수 문제

문자열 → 개수 세기

---

2. Map 활용

map.getOrDefault(key, 0) + 1

---

3. 사전순 비교

str1.compareTo(str2)

---

4. 정렬 vs Map

상황	추천
빈도수 + 정렬 필요	Map
연속 비교 가능	정렬

---

시간 복잡도

방식	복잡도
내 코드 (TreeMap)	O(N log N)
강의 코드 (HashMap)	O(N)
강의 코드 (정렬)	O(N log N)

---

정리

이 문제는 단순 문자열 문제처럼 보이지만
핵심은 다음이다.

문자열 개수 세기 + 최대값 찾기 + 사전순 처리

내 코드는 TreeMap을 사용해서
정렬을 자동으로 처리한 것이 특징이다.

강의 코드에서는

• HashMap으로 빠르게 처리하거나
• 정렬 후 연속 구간으로 처리하는 방식

을 사용했다.

핵심 차이는 다음과 같다.

내 코드   → 정렬을 자료구조에 맡김
강의 코드 → 비교를 직접 구현

이 문제를 통해

자료구조 선택에 따라 구현 방식이 달라진다

는 점을 배울 수 있다.