[Programmers] #120812 - 최빈값 구하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

정수 배열 array가 주어질 때 가장 자주 나오는 값을 찾되, 그런 값이 여러 개면 -1을 반환하면 되는 문제다. array의 원소가 0 이상 1000 미만으로 제한되므로, 값별 등장 횟수를 크기 1000짜리 배열(또는 해시맵)에 세어두고 가장 큰 카운트를 가진 값을 찾으면 된다. 이때 최댓값 카운트를 가진 값이 둘 이상이면 -1을 반환해야 한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = array의 길이. 값의 범위가 0 이상 1000 미만으로 고정되어 있어 카운트 배열/해시맵의 크기는 입력 크기와 무관하게 상수다)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[] array) {
        int[] cnt = new int[1000];
        for (int x : array) {
            cnt[x]++;
        }

        int ans = -1;
        int max = 0;
        boolean flag = false;
        for (int i = 0; i < 1000; i++) {
            if (cnt[i] > max) {
                ans = i;
                max = cnt[i];
                flag = true;
            } else if (cnt[i] == max) {
                flag = false;
            }
        }

        if (flag) return ans;
        return -1;
    }
}

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

int cnt[1000];

int solution(vector<int> array) {
    for (int x : array) cnt[x]++;

    int ans = -1;
    int mx = 0;
    bool flag = false;

    for (int i = 0; i < 1000; i++) {
        if (cnt[i] > mx) {
            ans = i;
            mx = cnt[i];
            flag = true;
        } else if (cnt[i] == mx) {
            flag = false;
        }
    }

    if (flag) return ans;
    return -1;
}

from collections import Counter


def solution(array):
    top2 = Counter(array).most_common(2)
    if len(top2) == 1 or top2[0][1] != top2[1][1]:
        return top2[0][0]
    return -1

collections.Counter로 등장 횟수를 센 뒤 most_common(2)로 빈도 상위 2개를 뽑는다. 배열에 서로 다른 값이 하나뿐이면 top2의 길이가 1이 되므로 그 값을 그대로 반환하고, 둘 이상이면 1위와 2위의 등장 횟수를 비교해 같으면 최빈값이 여럿이라는 뜻이므로 -1을, 다르면 1위 값이 유일한 최빈값이므로 그 값을 반환하면 된다.

---