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

문제 링크

1302번: 베스트셀러

문제 요약

하루 동안 판매된 책의 이름이 나열될 때, 가장 많이 팔린 책의 이름을 출력해야 한다.

접근 방법

std::map을 이용하면 쉽게 해결할 수 있습니다.

입력을 받으면 맵의 내부에 해당 Key가 존재하는지 확인하고, 만약 존재하지 않는다면 value를 0으로 해서 삽입합니다. Key가 존재한다면 대응되는 value를 1 증가시키면 됩니다.

문제에서는 '가장 많이 팔린 책이 여러 개인 경우 사전 순으로 가장 앞서는 제목을 출력한다.'고 되어 있습니다.

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

C++ 레퍼런스에 위와 같이 적혀 있듯이, std::map은 내부적으로 정렬이 됩니다. 따라서 std::map에 입력을 모두 마치면, 처음부터 이동하면서 최댓값을 찾으면 됩니다. 그러면 자연스레 사전 순으로 가장 앞서는 제목을 찾을 수 있습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	map<string, int> m;
	while (n--)
	{
		string str;
		cin >> str;

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

	int max = 0;
	string res;
	for (auto& i : m)
		if (i.second > max)
			res = i.first, max = i.second;

	cout << res;
	return 0;
}