해당 포스팅은 백준 1302번 베스트셀러 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였다.
문제
문제 설명
김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.
오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.
출력
첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.
풀이
오늘 팔린 책들이 입력으로 들어올 때 책들의 이름과 개수를 해시로 저장한 다음, 가장 value가 큰 값을 출력해야 한다. 문제에서 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력하라고 명시되어 있으므로 처음 input을 정렬해주어야 한다.
예제를 통해 로직을 자세하게 설명하겠다.
로직 & 예제 설명
문제의 예제2를 통해 자세한 로직을 설명하겠다.
위의 예제의 input을 파싱하면 다음과 같다.
- 하루 동안 팔린 책의 개수 N = 8
- 팔린 책들의 제목 books = [
'icecream', 'peanuts',
'peanuts', 'chocolate',
'candy', 'chocolate',
'icecream', 'apple'
]
문제에서 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력하라고 명시되어 있으므로 books를 오름차순 정렬해준다. 오름차순을 해주어야 하는 이유는 후에 설명하겠다.
- 오름차순 정렬 books = [
'apple', 'candy',
'chocolate', 'chocolate',
'icecream', 'icecream',
'peanuts', 'peanuts'
]
가장 많이 팔린 책을 변수 maxBook로 저장한 다음, 먼저 books[0]으로 초기화한다.
그 다음 오늘 팔린 책들의 이름과 개수를 해시dict로 저장하기 위해 books를 loop 돌린다.
현재 원소 book이 이미 해시에 저장되어 있는 경우 dict[book] += 1으로 값을 하나 늘려준다. 만약 저장되어 있지 않은 경우 dict[book] = 1을 해준다.
그 다음 maxBook의 값보다 현재 원소book의 값이 더 클 경우(더 많이 팔린 경우) maxBook을 현재 원소 book으로 업데이트 해준다. 이 때 앞서 input을 오름차순 정렬해주었기 때문에 값이 같을 때에는 사전순으로 앞선 값이 maxBook이 될 수 있다.
이를 코드로 구현하면 다음과 같다.
const dict = {};
let maxBook = books[0];
for (let book of books) {
if (book in dict) dict[book] += 1;
else dict[book] = 1;
if (dict[maxBook] < dict[book]) maxBook = book;
}예제의 경우 dict는 { apple: 1, candy: 1, chocolate: 2, icecream: 2, peanuts: 2 }이다. 초콜릿과 아이스크림, 피넛은 값이 같으나 사전순으로 앞선 값이 maxBook이므로 chocolate이 maxBook이 된다.
전체 풀이
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n').slice(0, -1);
const n = Number(input.shift());
const books = input.sort();
const dict = {};
let maxBook = books[0];
for (let book of books) {
if (book in dict) dict[book] += 1;
else dict[book] = 1;
if (dict[maxBook] < dict[book]) maxBook = book;
}
console.log(maxBook);