[정렬] 11652. 카드

1. 문제 해결 전략

map을 사용하면 쉽게 풀린다. 처음에 class를 정의하여 count와 number를 멤버로 넣고 operator 연산을 넣어서 정렬후 접근하는 방식을 사용하려 했는데, count는 외부에서 결정되어야 한다는 것을 깨닫고 count를 중복된 number에 증가시키는 방법을 생각하다가 map을 떠올리게 됐다. 참고로 map은 key에 따라서 자동 정렬이 이루어진다.

 

#include <iostream>
#include <algorithm>
#include <map>

long long int ans[100001];

int main(void)
{
	int n;
	std::map<long long int, int> m;
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		std::cin >> ans[i];
		if (m.find(ans[i]) == m.end())
		{
			m.insert(std::make_pair(ans[i], 1));
		}
		else
		{
			m[ans[i]]++;
		}
	}

	int val = 0;
	long long int ans = 0;
	for (auto iter = m.begin(); iter != m.end(); ++iter)
	{
		if (val < (*iter).second)
		{
			val = (*iter).second;
			ans = (*iter).first;
		}
	}

	std::cout << ans << std::endl;
}

중간에 map에 insert하는 부분을 설명하자면, 반복자가 end까지 갔다면 해당 원소가 map에 없다는 것으로 [number, 1] (count는 처음 들어가는 원소에 1을 대입한다.) 형식으로 insert하고 이미 key가 존재한다면 해당 key에 대한 값(count)을 1 증가시킨다.

 

그리고, map 원소들을 순회하며 count값을 비교하고, 가장 큰 값을 ans에 넣어준다. 여기서 아까 언급한 map은 자동으로 정렬되는 성질에 의해서 차례대로 원소를 순회하면 first값은 정렬된 상태로 들어가게된다. 따라서 첫번째 number의 count 값과 두번째 number의 count 값만의 비교를 통해서 문제의 조건인 count가 큰 number, count가 같은경우 더 작은 number를 답으로하는 조건을 동시에 만족시킬 수 있는 것이다.

 

2. 걸린 시간

1시간

 

3. 느낀점

두 달만에 다시 알고리즘 문제를 풀어서 그런지 처음에 감을 못잡았다. 문제 자체는 쉬웠는데 예전에 map을 사용하다 시간 초과가 걸린적이 있어서.. 아이디어는 떠올랐지만 다른 길을 선택해서 실패를 여러번 했다.

 

4. 링크

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