백준 11652. 카드

카드

정렬 관련 문제인데, 해시로도 풀이 가능한 문제

1. 간단 설명

---

N장의 카드를 뽑는데, 중복 숫자가 나온다

가장 개수가 많은 카드의 번호를 출력하는 문제

2. 예시

---

5 1 2 1 2 1 5개의 카드가 주어짐

1은 3장, 2는 2장이므로, 1이 제일 많아 1을 출력하면 된다

주의사항

• 가장 많이 가지고 있는 카드가 여러개라면, 작은것을 출력

3. 알고리즘

---

해시를 이용한 풀이

unordered_map을 사용해서 풀이했음

1. N 입력받기
2. 카드 번호(정수)를 입력받는다
	2-1. 이미 존재한다면 개수를 +1 해준다
	2-2. 존재하지 않는다면, 새로 추가해주고 값을 1로 세팅한다
3. 전체 해시를 탐색하며 가장 개수가 많은 카드를 찾는다

정렬을 이용한 풀이

또는 그냥 간단히 정렬로도 풀이가 가능하다

1. N 입력받기
2. 카드 입력받기
3. 카드를 오름차순으로 정렬
4. 첫번째 원소부터 탐색하며 최빈값 탐색

4. 소스코드

---

해시를 이용한 풀이

#include <iostream>
#include <unordered_map>

using namespace std;

int N;
unordered_map<long long int, int> um;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		long long int num; cin >> num;
		um[num]++;
	}

	long long int max_num = -(1LL << 62); // 비트 연산을 이용해 최소값을 -2^62로 초기화
	int max_cnt = 0;
	for (const auto& n : um) {
		if (max_cnt < n.second) {
			max_num = n.first;
			max_cnt = n.second;
		}
		else if (n.second == max_cnt && n.first < max_num) {
			max_num = n.first;
		}
	}
	cout << max_num << '\n';
}

unordered_map을 이용했으므로, 값이 정렬되어있지 않다

오름차순이라면 쭉 비교하면서 개수가 같다면 무시해도 상관없지만

정렬되어있지 않으므로, 같은 개수가 오히려 더 숫자가 작은 카드일수도 있으므로, 이를 체크해주는 과정이 필요하다

정렬을 이용한 풀이

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

using namespace std;

int N;
vector<long long int> v;

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; i++) {
		long long int num; cin >> num;
		v.push_back(num);
	}

	sort(v.begin(), v.end(), less<long long int>()); // 오름차순 정렬

	// 최빈값 찾기
	long long mode = v[0];
	int max_count = 1, current_count = 1;

	for (int i = 1; i < N; i++) {
		if (v[i] == v[i - 1]) {
			current_count++;
		}
		else {
			current_count = 1;
		}

		if (current_count > max_count) {
			max_count = current_count;
			mode = v[i];
		}
	}

	cout << mode << '\n';
}

오름차순으로 정렬되어있으므로, 같은 카드들은 연속으로 배치되어있음

이를 이용해서 최빈값을 찾는다