백준 1302번 Pseudo code

문제 링크

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

1302번: 베스트셀러

 

시간 제한 / 메모리 제한

2 초

128 MB

 

문제

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

예제 입력

5
top
top
top
top
kimtop

예제 출력

top

문제 풀이를 위해 생각한 것

1. 어떤 자료구조를 쓸 것인가? 맵?
2. 가장 많이 팔린 책이 여러 개일 경우에는 어떻게 할 것인가?
3. 우선 맵을 사용해서 각 책이 팔린 횟수를 담는다.
4. 맵을 튜플 배열의 형태로 변환 후 정렬한다. 한 번은 value(팔린 책) 기준으로, 다음은 알파벳 기준으로.

 

사용한 자료구조

맵 및 배열 자료구조.

책의 판매 횟수를 각각 저장할 때는 삽입의 시간 복잡도가 O(1)인 맵 자료구조를 사용.

책의 판매 횟수와 이름을 정렬할 때는 배열 자료구조 활용. 맵은 해시 테이블을 활용해 데이터를 저장하고 있으며, 순서를 알 수 없기에 그 자체로는 정렬이 불가하다. 따라서 이를 (key, value) 튜플의 리스트로 만들어 정렬할 수 있다. 

파이썬 dict 정렬

 

풀이 코드

n = 첫 입렧값을 정수로
map = 맵 선언

n번 동안:
	map[입력값] += 1 # (맵 자료구조가 파이썬의 defaultdict과 같은 성질이라고 가정)

arr = map을 튜플 배열로 변환하여 저장

팔린 횟수 기준 arr 내림차순 정렬
알파벳 기준 arr 오름차순 정렬

print arr[0]

 

시간 복잡도 분석

O(NlogN).

 

맵 자료구조의 삽입은 O(1). 이를 N번 반복하여 O(N).

맵을 배열로 변환하는 연산 또한 O(N).

2회의 정렬은 각각 O(NlogN).

 

최대차항이자 이 알고리즘의 시간 복잡도는 O(NlogN).

 

문제에서 중요한 부분

답을 도출하기 위해서는 정렬을 두 번 수행해야 하며, 맵 자료구조는 정렬이 불가하기에 배열의 형태로 변환한 후 정렬을 수행해야 한다.