📚 딕셔너리를 활용한 베스트셀러 찾기 알고리즘

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

백준 1302번 베스트셀러 문제는 가장 많이 팔린, 즉 판매량이 가장 높은 책을 찾는 문제입니다. 이 문제의 핵심은 딕셔너리를 활용해 판매량을 효과적으로 계산하고, 조건에 맞는 결과를 출력하는 데 있습니다.

🔍 문제 이해와 해석

1. 문제 요구사항

– 오늘 판매된 책들 중 가장 많이 팔린 책의 제목을 출력

– 가장 많이 팔린 책이 여러 개일 경우 사전순으로 가장 앞서는 책을 출력

– 입력은 1,000개 이하의 자연수 N(책의 개수)과 N개의 책 제목으로 구성

2. 테스트 케이스 분석

– 예제 1: “top”이 4번 팔려 가장 많이 팔린 책으로 선정되었다

– 예제 3: “a”와 “b”가 각각 3번씩 팔려 공동 1위이나, 사전순으로 “a”가 앞서므로 “a” 출력

– 예제 4: “icecream”, “peanuts”, “chocolate”이 각각 2번씩 팔려 공동 1위이나, 사전순으로 “chocolate”이 가장 앞서 “chocolate” 출력

💡 알고리즘 설계 전략

1. 자료구조 선택

– 딕셔너리(해시맵)를 사용하여 책 제목(키)과 판매량(값)을 관리

– 딕셔너리의 키-값 쌍을 이용해 효율적으로 판매량 집계 가능

2. 알고리즘 흐름도

`1. 빈 딕셔너리 생성 2. 각 책 입력 받을 때마다:

• 딕셔너리에 해당 책이 있으면 판매량 1 증가
• 없으면 딕셔너리에 새로 추가하고 판매량 1로 설정

3. 딕셔너리 값 중 최댓값(가장 많이 팔린 권수) 찾기
4. 최댓값과 같은 판매량을 가진 책들을 리스트에 추가
5. 리스트 사전순 정렬
6. 정렬된 리스트의 첫 번째 요소 출력`

🧩 코드 구현과 설명

1. 입력 처리와 딕셔너리 초기화

import sys
input = sys.stdin.readline

d = dict()
for _ in range(int(input())):
    book = input().rstrip()
    if book in d:
        d[book] += 1
    else:
        d[book] = 1

– sys.stdin.readline을 사용해 입력 속도 개선

– 딕셔너리를 이용해 책 제목과 해당 책의 판매량을 기록

2. 최다 판매 책 찾기

m = max(d.values())
candidates = []
for k, v in d.items():
    if v == m:
        candidates.append(k)
candidates.sort()
print(candidates[0])

– **d.values()**로 모든 판매량을 가져와 그 중 최댓값을 찾음

– 최다 판매량과 일치하는 책들을 후보 리스트에 추가

– 후보 리스트를 사전순으로 정렬하여 첫 번째 요소 출력

import sys
input = sys.stdin.readline

d = dict()
for _ in range(int(input())):
    book = input().rstrip()
    if book in d:
        d[book] += 1
    else:
        d[book] = 1
# print(d)
# 5
# top
# top
# top
# top
# kimtop
# {'top': 4, 'kimtop': 1}

m = max(d.values())
candidates = []
# print(m) # 4
for k,v in d.items():
    if v == m:
        candidates.append(k)
candidates.sort()
print(candidates[0])

📊 예제 실행 과정

1. 예제 입력 1 실행 과정

– 입력: “top” 4번, “kimtop” 1번

– 딕셔너리 상태: {'top': 4, 'kimtop': 1}

– 최대 판매량: 4권

– 후보 리스트: ['top']

– 출력: “top”

2. 예제 입력 3 실행 과정

– 입력: “a” 3번, “b” 3번

– 딕셔너리 상태: {'a': 3, 'b': 3}

– 최대 판매량: 3권

– 후보 리스트: ['a', 'b']

– 정렬 후: ['a', 'b']

– 출력: “a”

🔑 핵심 포인트 정리

1. 자료구조 활용

– 딕셔너리는 키-값 쌍을 저장하는 자료구조로, 책 제목과 판매량을 효율적으로 관리

– 시간 복잡도: 데이터 검색/삽입/삭제 모두 O(1) (평균)

2. 파이썬 기본 함수 활용

– max() 함수로 최댓값 찾기

– sort() 메서드로 사전순 정렬

– dict.items(), dict.values() 메서드로 딕셔너리 데이터 접근

3. 조건 처리

– 동일한 판매량을 가진 책이 여러 권일 경우 사전순 정렬을 통해 해결

– 판매된 책이 한 종류일 경우에도 정상 작동

🎯 응용 및 확장 가능성

1. 다양한 정렬 기준 적용

– 판매량이 같을 때 다른 기준(예: 가격, 출간일)으로 정렬하도록 확장 가능

– 복합 정렬 기준 적용: candidates.sort(key=lambda x: (x[1], x))

2. 실무 활용

– 실제 서점 POS 시스템에서의 베스트셀러 집계 로직으로 활용 가능

– 데이터 분석에서 빈도수 기반 처리에 응용 가능

이 문제는 딕셔너리 자료구조의 특성을 잘 활용한 문제로, 실생활의 데이터 집계 상황에서도 유사한 접근 방식을 적용할 수 있습니다.