최빈값 구하기 - Python

def solution(array):
    answer = -1
    num_list = [0 for _ in range(1001)]
    for item in array:
        num_list[item] += 1

    max_appear = max(num_list)
    for i in range(1001):
        if max_appear == num_list[i]:
            if answer == -1:
                answer = i
            else:
                answer = -1
                break
    return answer


# Test Cases
print(solution([1, 2, 3, 3, 3, 4]))
print(solution([1, 1, 2, 2]))
print(solution([1]))

  제 풀이는 위와 같습니다. 아래는 세부 설명입니다.

---

    num_list = [0 for _ in range(1001)]

  1. 수의 범위가 0부터 1000까지이므로 출현빈도값을 저장할 리스트를 만듭니다.

 

    for item in array:
        num_list[item] += 1

  2. 만들어진 리스트에 출현한 횟수만큼 1을 더해줍니다.

 

max_appear = max(num_list)

  3. 최빈값의 출현 빈도를 저장합니다.

 

    for i in range(1001):
        if max_appear == num_list[i]:
            if answer == -1:
                answer = i
            else:
                answer = -1
                break

  4. 이후 리스트를 돌며 최초로 최빈값의 출현 빈도와 같은 인덱스 값을 answer에 저장을 합니다. 이후 중복된 인덱스 값을 가질 경우 answer에 -1을 저장한 후 반복문을 종료합니다.

 

  위와 같이 네 단계로 구성하여 풀었습니다. 리스트는 반복문 하나를 통해 처리하므로 시간 복잡도는 O(N)입니다.

 

---

def solution(array):
    while len(array) != 0:
        for i, a in enumerate(set(array)):
            array.remove(a)
        if i == 0: return a
    return -1

  이건 다른 사람의 풀이입니다. 접근 방법이 신선하여 소개합니다.  이 코드의 동작을 쉽게 이해하기 위해 아래와 같이 코드 한 줄을 추가하였고 그 결과입니다.

def solution(array):
    while len(array) != 0:
        for i, a in enumerate(set(array)):
            array.remove(a)
            print(f"i: {i}, a: {a}") # 추가한 부분
        if i == 0: return a
    return -1


# Test Cases
print(solution([1, 2, 3, 3, 3, 4]))
print(solution([1, 1, 2, 2]))
print(solution([1]))


"""결과
i: 0, a: 1
i: 1, a: 2
i: 2, a: 3
i: 3, a: 4
i: 0, a: 3
3
i: 0, a: 1
i: 1, a: 2
i: 0, a: 1
i: 1, a: 2
-1
i: 0, a: 1
1

[Execution complete with exit code 0]
"""

  set을 통해 중복값을 없애주고, i를 통해 인덱스 값을 받아왔습니다. 그러나 시간 복잡도면에서 중첩 반복문을 통해 알고리즘을 구성하였으므로 O(N^2)입니다. 이는 리스트의 크기가 커질수록 소요 시간이 급증함을 의미합니다.

 

---

from collections import Counter

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

  또 다른 사람의 풀이입니다. 이 풀이는 Counter 함수를 사용했는게 인상적입니다. a = Counter(array).most_common(2) 를 통해 최빈값 두 개를 a에 저장하였고, a의 길이에 따라 정답을 다르게 표현한게 재밌습니다. 찾아보니 이 코드의 경우 시간 복잡도는 O(N + N*logN) 이므로 대략적으로 O(N*logN)이라고 합니다.

 

---

def solution(array):
    answer = 0
    idx = [0] * 1001
    for i in array:
        idx[i] +=1
    if idx.count(max(idx)) >1:
        return -1
    return idx.index(max(idx))

  마지막으로 하나의 풀이만 더 소개하겠습니다. 이 풀이는 제 풀이와 방향성은 같지만, 보다 훨씬 좋은 풀이입니다.

 

---

• 프로그래머스: https://school.programmers.co.kr/learn/courses/30/lessons/120812

프로그래머스