BOJ 11652 카드

boj 11652 카드

간단하게 모든 카드의 수를 세보는 O(N^2) 풀이법이 가장 먼저 떠오르지만, 시간 초과이다. 일단 먼저 정렬을 하여 같은 값들을 다 붙였다. 그리고 mxval는 현재까지 가장 많이 등장한 수의 값, mxcnt는 현재까지 가장 많이 등장한 수의 등장한 횟수, cnt는 현재 보는 수가 등장한 횟수를 의미하고, mxval = -2^62-1, mxcnt = 0, cnt = 0으로 초기화하였다. 현재 보는 수가 제일 앞의 수이거나 직전의 수와 같은 값이면 cnt를 1 증가시킨다. 그리고 직전의 수와 다른 값을 가지면 cnt를 다시 1로 초기화시켜준다. cnt가 mxcnt보다 커지면 mxval과 mxcnt를 바꿔준다. 시간복잡도는 정렬하는데 O(NlogN)이고 카드들의 수를 보는데 O(N)이므로 최종적으로 O(NlogN)이다.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long a[100005];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n);
    int cnt = 0;
    long long mxval = -(1LL << 62) - 1;
    int mxcnt = 0;

    for (int i = 0; i < n; i++) 
    {
        if (i == 0 || a[i - 1] == a[i]) cnt++;
        else 
        {
            if (cnt > mxcnt) 
            {
                mxcnt = cnt;
                mxval = a[i - 1];
            }
            cnt = 1;
        }
    }

    if (cnt > mxcnt) mxval = a[n - 1];
    cout << mxval;

    return 0;
}