[백준/C++]#11652 - 카드

풀이

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

using namespace std;

int main() {
	int n;
	cin >> n;
	vector <long long> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	stable_sort(a.begin(), a.end());
	int cnt=1, before=1; 	// 비교할 변수 정의
	long long k = a[0];		// 초기값 대입
	for (int i=1; i<n; i++) {
		if (a[i]==a[i-1]) {
			cnt++;
		}
		else	
			cnt = 1;
		if (before < cnt) {		// 새로운 값의 빈도수가 더 클 때
			before= cnt;
			k= a[i-1];
		}
	}
	cout << k;
	
	return 0;
}

개념

2^-62부터 2^62까지 범위의 정수는 long long 변수형을 통해 나타낼 수 있다.

 

---

풀이 

 

이전 문제와 비슷하게 접근할수도 있겠다고 생각했으나, 수의 범위가 매우 크다.

따라서 모든 수에 해당하는 index를 가진 배열은 만들 수 없다.

 

가장 많이 등장하는 숫자를 찾기 위해서는 수의 비교가 필수적이다.

수를 정렬하면, 빈도수를 비교하기 편해질 것이다.

무질서하게 존재하면, 각 수를 비교할 때 index 참조를 위해 O(N)만큼 더 계산해줘야하기 때문이다.

 

따라서 stable_sort를 사용해 정렬을 완료했다.

이제 정렬된 a 배열에서 가장 큰 빈도수의 값을 구해야한다.

왼쪽에서 오른쪽으로 가며, 반복문 내에서 if문을 통해 값이 달라지는 시점을 찾아낸다.

 

왼쪽에서 오른쪽으로 이동하며 최댓값을 구하는 문제와 마찬가지로, 두 개의 변수를 이용해서 꾸준히 비교할 수 있다. 

---

+a

위와 같이 vector를 사용하지 않아도 배열(ex. a[100000])을 통해 정렬해도 된다.

카드의 수 (n)가 100,000 밖에 되지 않아서 그렇다.

 

다른풀이(from 백준github)

#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    map<long long, int> d;
    while (n--) {
        long long x;
        scanf("%lld",&x);
        d[x] += 1;
    }
    int m = 0;
    long long ans = 0;
    for (auto &p : d) {
        if (p.second > m) {
            m = p.second;
            ans = p.first;
        } else if (p.second == m && p.first < ans) {
            ans = p.first;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

map을 사용한 풀이이다. map은 first (key)와 second (value)가 있는 pair 객체로 저장된다.

자료저장시 key를 기준으로 오름차순으로 자동 정렬된다.

 

그를 이용한 것이고, for문의 (auto &p : d) 는 범위기반 for문(ranged-based for statement)이다.

배열의 모든 요소를 반복하는데 더욱 간단하고 안전하다!

---

for 문 내에서 두 변수 before와 cnt를 구성해 비교할 수 있게 하는 것은 어렵지 않았다.

그에 해당하는 배열의 값을 참조하는 것이 어려웠다.

변수의 비교와, 값 참조는 별개로 느껴졌는데, if문 밖에 또 다른 if문을 구성해 해결할 수 있었다.

 

문제에 나와있는 예제의 경우, before와 cnt의 비교가 한번밖에 이뤄지지 않는다.

이런 경우, 혹은 아예 이뤄지지 않는 경우를 대비해 long long k = a[0]; 문장이 필요하다.