[백준 11652번 C++] 카드 (Map 활용)

문제

문제 분석

이 문제를 해결하기 위해 가장 먼저 배열로 담아서 인덱스로 접근하는 방법을 생각할 수 있다.

하지만 이 문제에서 배열로 담아서 인덱스로 접근하는 방법을 구현할 경우 -2^62~2^62의 값을 담을 수 있는 공간을 미리(선언부터) 할당해야 한다.

누가봐도 메모리 초과가 나올게 뻔하다.

map과 set은 insert 연산을 통해서 데이터를 삽입할 때 공간을 할당하므로 N이 최악의 경우 100000 이어도 메모리 초과가 나지 않는다.

정답 코드

- map의 value 값을 정렬하기 위해서 map의 값을 vector로 옮겨 정렬하였다.

// 1안 )배열 인덱스를 활용 -> 배열은 먼저 메모리에 할당을 해놔야 하기 때문에 수의 범위가 -2^62~2^62인 숫자들을 담을 공간을 마련하려면 메모리 초과가 뜰 것이다.
// 2안 )unordered_map을 활용 -> insert가 들어오면 그때서야 메모리에 할당을 하고 데이터를 넣는다. 넣어야 할 숫자 카드 개수는 최악의 경우에도 10만개이므로 메모리 우려를 해결할 수 있다.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(const pair<long long, int>& p1, const pair<long long, int>& p2) {
	if (p1.second != p2.second) return p1.second > p2.second; // 카드 개수 순으로 내림차순 정렬
	return p1.first < p2.first; // 카드 숫자 순으로 오름차순 정렬
}

unordered_map<long long, int> um; // (카드 숫자, 카드 개수)

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		long long card_num;
		cin >> card_num;
		um[card_num]++;
	}
	
	vector<pair<long long,int>> v(um.begin(), um.end()); // unordered_map 정렬을 위해 만든 임시 벡터 - unordered_map에 있는 값을 vector에 옮긴다.
	sort(v.begin(), v.end(), cmp);
	cout << v[0].first; // 정답 출력
	return 0;
}