백준 1302 - 베스트셀러 (파이썬)

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

풀이

진짜 어마어마 하게 쉬운문제이다.

N개의 책 제목이 주어질 때, 가장 많이 팔린 책의 제목을 출력하되, 여러 개라면 사전순으로 가장 앞서는 제목을 출력하는 문제이다.

시간 복잡도 분석

1. N개의 책 제목을 입력받으면서 딕셔너리에 저장하는 과정 → O(N)
2. count.items()를 순회하면서 최대값을 찾는 과정 → O(M)
3. 최악의 경우 O(N + M) 이기에 매우 효율적

코드

# 백준 1302 - 베스트셀러
# 분류 : 문자열, 정렬

N = int(input())

count = {}
for _ in range(N) :
    title = input()

    if title not in count :
        count[title] = 0
    count[title] += 1

max_value = 0
max_title = ""
for key, value in count.items() :
    if max_value < value :
        max_value = value
        max_title = key
    elif max_value == value :
        if max_title > key :
            max_title = key

print(max_title)