파이썬 백준 알고리즘 - 인기 있는 책 찾기 풀이 해석

안녕하세요! 알고리즘을 사랑하는 여러분, 반갑습니다. 오늘은 "인기 있는 책 찾기" 문제를 다뤄보려고 합니다. 이 문제는 주어진 도서 목록에서 가장 많이 팔린 책의 이름을 찾는 문제입니다. 풀이 방법과 코드를 통해 자세히 알아보겠습니다. 그럼 시작해봅시다!

문제 내용

주어진 도서 목록에서 가장 많이 팔린 책의 이름을 출력해야 합니다.

문제 이해하기

주어진 입력은 도서의 개수 **N**과 도서 목록입니다. 도서 목록에서 각 책의 이름을 읽고, 해당 책의 판매량을 계산하여 가장 많이 팔린 책의 이름을 출력합니다.

풀이 코드

pythonCopy code
N = int(input())

books = {}
for _ in range(N):
    name = input()
    if books.get(name):
        books[name] += 1
    else:
        books[name] = 1

bookItem = list(books.items())
bookItem.sort(key=lambda x: (-x[1], x[0]))

print(bookItem[0][0])

풀이 방법

해당 문제를 해결하기 위해 다음과 같은 풀이 방법을 사용합니다.

1. 입력 값으로 도서의 개수 **N**을 받습니다.
2. 빈 딕셔너리인 **books**를 생성합니다.
3. **N**번 반복하면서 도서의 이름을 입력받습니다.
4. books 딕셔너리에서 해당 책의 이름이 이미 존재한다면, 판매량을 1 증가시킵니다.
5. 책의 이름이 books 딕셔너리에 존재하지 않는다면, 새로운 항목으로 추가하고 판매량을 1로 설정합니다.
6. books 딕셔너리를 (이름, 판매량) 형태로 변환한 후, 판매량을 기준으로 내림차순으로 정렬합니다. 판매량이 동일한 경우, 이름을 오름차순으로 정렬합니다.
7. 정렬된 리스트에서 가장 많이 팔린 책의 이름을 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(NlogN)입니다. 도서의 개수 **N**에 비례하여 반복문이 실행되기 때문에 O(N)의 시간이 소요됩니다. 그리고 books 딕셔너리를 리스트로 변환하는 과정과 정렬하는 과정에서 O(NlogN)의 시간이 소요됩니다. 따라서, 전체적으로 O(NlogN)의 실행 시간이 소요됩니다.

이상으로 "인기 있는 책 찾기" 문제의 풀이를 설명하는 포스트를 마치겠습니다. 알고리즘에 대한 이해와 함께 문제 해결 능력을 향상시킬 수 있기를 바라며, 다음 포스트에서 더 다양한 알고리즘 문제를 다뤄보도록 하겠습니다. 감사합니다!

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음