[BOJ] 백준 #1302. 베스트셀러 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/1302

• 알고리즘 분류: 자료구조
• 난이도: Silver Ⅳ

💬 풀이

문제를 읽자마자 생각난 자료구조 =맵(map)!

1. 입력받은 책제목들과 그 빈도 수를 각각 key, value로 하는 맵을 만들어 이용한다.
2. 입력받은 책제목들을 맵 변수에 insert한다.
3. map은 기본적으로 key값 기준 오름차순 정렬되는데, greater를 이용해 내림차순 정렬로 설정한다.
4. 이미 내림차순 정렬되어 있으므로 그 순서대로 max값을 갱신해주면 자동으로 사전 순 가장 앞서는 제목을 얻을 수 있다.

👩‍💻 코드

C++

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

int main() {
	//freopen("input.txt", "rt", stdin);
	int N;
	cin >> N;
	map<string, int, greater<string>> m;
	string s;
	while (N--) {
		cin >> s;
		if (m.count(s)) {
			m.find(s)->second += 1;
		}
		else {
			m.insert({ s,1 });
		}
	}

	int max_value = -1;
	string max_key;
	for (auto i = m.begin(); i != m.end(); i++) {
		int t_max = max(max_value, i->second);
		if (t_max == i->second) {
			max_value = t_max;
			max_key = i->first;
		}
	}
	cout << max_key;

	return 0;
}