[BOJ/C++] 11652번 카드

https://www.acmicpc.net/problem/11652

문제해석

 

첫 번째 줄에 N을 입력한다.

이후 두번째 줄부터 N+1째 줄에는 숫자 카드에 적혀있는 정수를 입력한다.

입력받은 정수 중 가장 많이 나온 정수를 출력한다.

(단, 가장 많이 나온 정수의 수가 같은게 있다면, 더 작은 정수를 출력한다.)

 

---

코드

 

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

unordered_map<long long, int> hash_map;
long long Key, result = 0;
int N;

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Key;
        hash_map[Key]++;
    }

    vector<pair<long long, int>> vec(hash_map.begin(), hash_map.end());

    sort(vec.begin(), vec.end(),
         [](const auto &a, const auto &b)
         {
             if (a.second == b.second)
                 return a.first < b.first;
             return a.second > b.second;
         });

    cout << vec[0].first << "\n";
}

---

문제 풀이

 

두 번째 줄부터 입력받을 수 있는 수의 범위가 -2^62부터 2^62까지이다.

따라서 두 번째 줄부터 입력받는 변수는 int가 아니라 long long을 사용한다.

 

또한 수의 범위는 |2^63|이므로, 최악의 경우 키를 찾기 위해 O(N)시간을 들여 push_back하는 것 보다 O(1)의 시간복잡도를 가지는 unordered_map을 이용해 key값(정수)와 value값(나온 횟수)로 저장한다.

 

이후 이렇게 입력받은 unordered_map을 복사해 vector로 만들고, sort함수를 이용해 정렬해준다.

 

또는 for문을 통해 입력받은 unordered_map을 바로 비교하는 방법도 있다.

 

이 경우 vector 변수를 따로 만들지 않아도 되기 때문에 시간복잡도 및 공간복잡도가  장점이 있다.

(sort함수의 경우 O(nlogn), for문의 경우 O(n)이기 때문)