[C++] 백준 1302번 베스트셀러

1. 문제이해

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

1302번: 베스트셀러

 

하루동안 팔린 책의 개수(N)과 팔린 책들의 이름이 주어진다.

이때, 가장 많이 팔린 책의 이름을 출력하는 것이 목표이다.

(단, 가장 많이 팔린 책이 여러 개일 경우, 사전 순으로 가장 앞서는 제목을 출력한다.)

 

 

 

2. 문제풀이

 

팔린 책의 개수(N)와 책의 이름들이 주어질 때, 가장 많이 팔린 책의 이름을 구하는 것이 목표이다.

책의 이름과 해당 책의 판매량을 모두 저장해야하기 때문에, 필자는 map container를 이용했다.

 

map은 key와 value가 쌍으로 저장되는 컨테이너로, 노드 기반의 균형 이진트리 구조를 가진다.

입력시, key는 고유한 값으로 중복이 불가능하며, key값을 기준으로 자동으로 오름차순 정렬된다.

map container는 아래와 같은 형태로 선언한다.

 

map< [Data type1], [Data type2] > [변수이름];

map에 대한 자세한 설명은 아래 블로그에서 잘 설명해주셨으니, 참고하도록 하자.

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법

 

 

해당 문제에서는 팔린 책의 이름과 판매량을 함께 저장해야한다.

key값은 중복되지 않는 고유한 값이므로,

필자는 map의 key값에 해당하는 부분에 책의 이름, value값에 해당하는 부분에 책의 판매량

을 선언해주었다. ( map <string, int> book; )

위와 같이 map형태로 선언해준 다음부터는 간단하다.

 

1.

책의 이름을 입력받고, 동일한 책이 있다면 해당 책의 판매량을 증가시키고,

아니라면 새로 값을 생성해준다.

 

2.

가장 많이 팔린 책의 판매량을 찾아 저장해두고,

 

3.

가장 많은 판매량을 가진 책의 이름을 찾으면 된다.

여기서, map은 key값, 책 이름을 기준으로 오름차순 정렬되어있다.

for문을 통해 앞에서부터 가장 많은 판매량을 가진 책을 찾게 되면,

가장 많은 판매량을 가진 책이 여러 개일 경우, 사전순으로 가장 앞서는 책이 출력된다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	int N;
	map <string, int> book;
	string input;
	int max_sales_rate;
	string best_seller;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;

		// 1. 입력받은 책과 동일한 책이 없는 경우
		if (book.find(input) == book.end()) {
			book.insert({ input, 1 });
		}
		// 2. 입력받은 책과 동일한 책이 있는 경우
		else {
			book[input]++;
		}
	}

	// 1. 가장 많이 팔린 책의 판매량 찾기
	max_sales_rate = 0;
	for (auto i = book.begin(); i != book.end(); i++) {
		max_sales_rate = max(max_sales_rate, i->second);
	}

	// 2. 가장 많은 판매량을 가진 책의 이름을 찾기
	// map은 key값을 기준으로 자동 정렬. 즉, 책 이름 순으로 정렬되어있음.
	// 가장 많이 팔린 책이 여러개여도 사전순으로 앞서는 것으로 출력됨.
	for (auto i = book.begin(); i != book.end(); i++) {
		if (max_sales_rate == i->second) {
			best_seller = i->first;
			break;
		}
	}

	cout << best_seller;

	return 0;
}

2. 문제풀이에서 도출한 방식에 따라 작성한 코드이다.

먼저, key값이 책 이름(string), value값이 판매량(int)인 형태의 map을 선언한다.

(map <string, int> book;)

책의 개수(N)와 책의 이름을 입력받고, 책의 이름을 입력받을 때마다 다음과 같은 과정을 거친다.

 

1 - 1. 동일한 이름의 책이 없는 경우

➡ 입력받은 책의 이름(input), 판매량은 1 로 하여 book(map)에 저장한다.

book.insert({ input, 1 });

 

1 - 2. 동일한 이름의 책이 있는 경우

➡ 입력받은 책의 이름(input)에 해당하는 판매량 값을 증가시킨다.

book[input]++;

 

책의 이름과 판매량을 위와 같은 형태로 저장한 뒤, 첫 번째 for문을 통해 1. 가장 많이 팔린 책의 판매량을 찾는다.

가장 많이 팔린 책의 판매량을 max_sales_rate로 선언, book에 저장된 판매량 값 중 가장 큰 값을 찾아나간다.

max_sales_rate = 0으로 초기화한 후, book에 저장된 판매량 값들과 비교해나가며

만약, max_sales_rate보다 판매량이 크다면, max_sales_rate를 해당 판매량 값으로 초기화한다.

위와 같은 과정을 반복하면, max_sales_rate는 가장 큰 판매량으로 초기화된다.

 

이후 두 번째 for문을 통해 2. 가장 많은 판매량을 가진 책을 찾는다.

첫 번째 for문을 통해 가장 많이 팔린 책의 판매량, max_sales_rate를 구했다.

이를 통해, max_sales_rate와 판매량이 같은 책을 찾고, 해당 책을 찾으면 best_seller 변수에 저장, break한다.

여기서, map은 key값인 책 이름으로 오름차순 정렬되어있기 때문에,

max_sales_rate값과 동일한 판매량을 가진 책이 여러개여도, 가장 사전순으로 앞서는 제목의 책이 나오게 된다.

이후 모든 연산을 마친 뒤, best_seller에 저장된 책 이름을 출력한다.

 

 

주석 없는 코드는 왼쪽 아래 더보기를 참고바랍니다.😊

<주석 없는 코드>

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	int N;
	map <string, int> book;
	string input;
	int max_sales_rate;
	string best_seller;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;

		if (book.find(input) == book.end()) {
			book.insert({ input, 1 });
		}
		else {
			book[input]++;
		}
	}

	max_sales_rate = 0;
	for (auto i = book.begin(); i != book.end(); i++) {
		max_sales_rate = max(max_sales_rate, i->second);
	}

	for (auto i = book.begin(); i != book.end(); i++) {
		if (max_sales_rate == i->second) {
			best_seller = i->first;
			break;
		}
	}

	cout << best_seller;

	return 0;
}

 

 

---

한동안 map을 사용하지 않았더니, 까먹고 있었다..🥺

이번 기회로 한번 더 공부하게 된것 같아 뿌듯한 문제였다.

 

문제에 대한 질문과 지적은 언제나 감사히 받고있습니다.😊