[BOJ / C++] 카드 (정렬)

문제링크: https://www.acmicpc.net/problem/11652

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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

    int n;
    cin >> n;

    vector<ll> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    ll cnt=1, mxcnt = 0, mxval = -(1ll<<62)-1;

    for (int i = 1; i < n; i++) {
        if (arr[i-1] == arr[i]) {
            cnt++;
        }
        else {
            if (cnt > mxcnt) {
                mxcnt = cnt;
                mxval = arr[i-1];
            }
            cnt = 1;
        }
    }
    if (cnt > mxcnt) mxval = arr[n-1]; // 마지막 수 처리 주의!

    cout << mxval;
}

 

 

2. 분석

숫자 범위가 -2^62 <= x <= 2^62 이므로 long long을 사용해야한다. sort를 통해 수를 같은 수를 인접하게 정렬하고, arr[i-1] != arr[i]인 부분을 찾아내서 mxcnt, mxval을 업데이트 하는 방식으로 가장 많은 숫자를 찾아낸다.

arr[i-1]과 arr[i]를 비교하므로 i < n까지 검사하면 arr[n]이 카운팅에서 빠지게 된다. 따라서 for문 이후 배열 마지막 수에 대한 처리를 해줘야한다.

 

3. 시간복잡도

n <= 10^5이므로 O(n^2)이면 10^10 > 10^7이므로 시간초과 판정을 받는다. 따라서 O(nlgn)까지 시간복잡도를 떨어뜨려야 10^6 < 10^7으로 시간 안에 해결이 가능하다. sort에서 O(nlgn)이고 배열을 순회하는데 O(n)이므로 전체 시간복잡도는 O(nlgn)이다.