Level 0. 최빈값 구하기

Level 0. 최빈값 구하기

 

 

첫 번째 풀이

 

map 내의 키가 정렬된 상태를 유지할 필요가 없기 때문에 레드-블랙 트리를 사용하는 map보다는 해시 테이블을 사용하는 unordered_map을 사용했다.

 

개수가 최대인 pair를 찾고 최댓값이 여러 개인지 확인하여 해결했다.

 

최댓값을 찾는 부분에서 O(n), 최댓값과 같은 값이 찾는 부분에서 O(n)이 소요되기 때문에 원소들을 2번 순회해야 한다.

 

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

using namespace std;

int solution(vector<int> array)
{
    int answer = 0;
    unordered_map<int, int> umap;

    for (int num : array)
        ++umap[num];

    unordered_map<int, int>::iterator maxIt = max_element(umap.begin(), umap.end(), [](auto& a, auto& b) { return a.second < b.second; });

    return count_if(umap.begin(), umap.end(), [maxIt](auto& a) { return a.second == maxIt->second; }) == 1 ? maxIt->first : -1;
}

 

두 번째 풀이

 

코드가 몇 줄 더 길긴 하지만 좀 더 개선된 풀이이다.

 

원소들을 2번 순회했던 첫 번째 풀이와 달리, 최댓값을 구함과 동시에 같은 값이 있는지 확인하기 때문에 1번만 순회해도 된다.

 

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int solution(vector<int> array)
{
    int answer = 0, maxCount = 0;
    unordered_map<int, int> umap;

    for (int num : array)
        ++umap[num];

    for (pair<int, int> pr : umap)
    {
        if (pr.second == maxCount)
        {
            answer = -1;
        }
        else if (maxCount < pr.second)
        {
            maxCount = pr.second;
            answer = pr.first;
        }
    }

    return answer;
}