알고리즘(C++) / 백준 11652 : 카드

11652

www.acmicpc.net/problem/11652

11652번: 카드

 

문제

준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -2^62보다 크거나 같고, 2^62보다 작거나 같다.

준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지고 있는 정수를 구하는 프로그램을 작성하시오. 만약, 가장 많이 가지고 있는 정수가 여러 가지라면, 작은 것을 출력한다.

 

입력

첫째 줄에 준규가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

 

출력

첫째 줄에 준규가 가장 많이 가지고 있는 정수를 출력한다.

 

코드

// 11652 카드
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
using namespace std;

bool compare(const pair<long long, int>& a, const pair<long long, int>& b) {
	if (a.second == b.second)
		return a.first < b.first;
	return a.second > b.second;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	map <long long, int> m;

	long long a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		m[a]++;

	}

	vector<pair<long long, int>> vec(m.begin(), m.end()); //map을 vector로 이동
	sort(vec.begin(), vec.end(), compare); //정렬

	cout << vec[0].first <<"\n";

	return 0;
}

 

설명

이번 문제는 숫자 카드의 입력을 longlong으로 입력받는 게 가장 중요하다.

적혀있는 수의 범위가 -2^62 ~ 2^62이므로 int형으로는 다 입력받을 수 없어서 longlong형으로 입력받아야 한다. 

 

map에 입력받은 수의 value 값을 1씩 증가시켜수 몇 개의 카드를 가지고 있는지 저장한다. 

map을 value값으로 정렬하기 위해 vector로 이동시킨 후 카드 개수의 내림차순으로 정렬하고 카드 개수가 같다면 작은 수로 정렬한다.

그렇게 가장 vector의 첫번째 값을 출력한다. 

 

결과

 

고찰

수의 범위를 확인하고 longlong으로 입력받아야 한다!!

vector로 입력받는 것보다 map으로 입력받는 게 편할 거 같아서 다음과 같이 구현하였다.

 

난이도

◐○○○○