백준 1302 베스트셀러 C++ 풀이

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

1302번: 베스트셀러

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.
오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

 

이 문제는 컨테이너인 map을 사용하면 아주 빠르고 간편하게 풀 수 있는 문제이다.

문제의 포인트

책의 숫자를 어떻게 저장할 것인가, 문제를 보고 map 자료구조를 떠올릴 수 있는가

map이란?

키(key)와 자료(value)를 저장, 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조이다.

c++ 에선 #include <map>을 통하여 사용할 수 있다.

 

map의 특징

전체 조회를 통해 key를 기준으로 오름차순으로 자동 정렬된 것을 확인할 수 있다.

중복 저장은 불가하다.

이는 균형 이진 검색 트리를 이용하기 때문에 발생하는 특징이다.

코드

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

int main()
{
	map<string, int> book;
	int len, max = 0;;
	string res,str;
	cin >> len;

	for (int i = 0; i < len; i++)
	{
		cin >> str;
		book[str]++; //책의 갯수 측정
	}

	for (auto curBook : book)
	{
		if (curBook.second >= max) //가장 큰 책의 갯수를 찾음
		{
			max = curBook.second;
			res = curBook.first;
		}
	}
	cout << res;
}

여담

map의 정렬을 vector를 이용하여 바꾸어 보려 하였으나 너무 비효율적인 코드가 되어 하나하나 돌아가며 가장 큰 값을

찾았다.