최빈값 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/120812

파이썬

3가지 방법으로 풀어보겠습니다. 

1. 리스트

기본적인 스타일로 코드를 작성한다면..
(max함수를 한 번 쓰긴 했지만)

def solution(array):
    times_list = [0] * (max(array) + 1)  # 리스트의 주소는 num, 원소는 num의 반복 횟수
    for num in array:
        times_list[num] += 1  # num이 나올 때 마다 1 증가
    mode = -1  # 최빈값은 영어로 mode
    mode_times = 0  # 최빈값의 횟수
    second_times = 0  # 최빈값이 1회 이상 나올 때, 그 횟수를 기록할 변수
    for index, times in enumerate(times_list):  # 인덱스와 횟수(times)를 동시에 뽑음
        if times > mode_times:  # 최대값보다 더 큰 값이 나오면...
            mode = index  # 그 주소는 새로운 최빈값이 됨
            mode_times = times  # 그 횟수는 최빈값의 횟수이 됨 
        elif times == mode_times:  # 최빈값과 같은 횟수가 나오면... 
            second_times = times  # 그 횟수를 기록해 두고 마지막에 비교. 
    if mode_times != second_times:  # second_times를 기록한 뒤에 새로운 mode_times가 기록이 되었다면 유일한 최빈값 
        return mode
    else:  # second_times와 mode_times 가 같으면 2개 이상의 최빈값이 있음. 
        return -1

간결하게 정리한다면 이 정도가 좋겠죠. 

def solution(array):
    times_list = [0] * (max(array) + 1)
    for num in array:
        times_list[num] += 1
    mode = -1
    mode_times = second_times = 0
    for index, times in enumerate(times_list):
        if times > mode_times:
            mode = index
            mode_times = times
        elif times == mode_times:
            second_times = times
    return mode if mode_times != second_times else -1

최댓값, 최솟값을 찾을 때 쓰는 기본적인 코드입니다. 

nums = (1, 2, 3, 4, 5)
max_num = float('-inf')  # 음의 무한대
for num in nums:
    if num > max_num:
        max_num = num
print(max_num)

파이썬의 max, min 함수가 속도도 빠르고 편하지만. 
이런 기본적인 코드도 알고 있어야 합니다. 
이런 코드를 알고 있어야,
최댓값이 여러 개일 때는 if num == max_num:이라는 조건을 사용하면 되겠네... 
라고 코드를 응용할 수가 있죠. 

리스트를 쓰더라도 파이썬 sort 메서드의 도움을 받는다면 간결해집니다. 

def solution(array):
    times_list = [[0, i] for i in range(max(array) + 1)]  # [빈도, 숫자]
    for num in array:
        times_list[num][0] += 1
    times_list.sort(reverse=True)
    return times_list[0][1] if times_list[0][0] != times_list[1][0] else -1

 

리스트의 문제점

이 문제에서 조건은 다음과 같습니다. 
0 ≤ array의 원소 < 1000

이 문제에서는 원소의 최대값이 999니까
최대 1000개의 원소를 담을 수 있는 리스트만 만들면 되지만..
만약 숫자 제한이 없다면, 숫자가 커질수록 필요 이상의 저장공간을 사용하게 됩니다. 
ex) (1,2,3, 10000000000) 
저장공간만 커질 뿐만 아니라 최대값을 찾기 위해 for문 등으로 검색할 때도 오랜 시간이 걸립니다. 

 

2. 딕셔너리

카운터로는 dict 자료형을 많이 이용합니다. (거의 정석입니다.)

def solution(array):
    times_dict = {}
    for num in array:
        if num not in times_dict:  #
            times_dict[num] = 0  #
        times_dict[num] += 1
    mode = -1
    mode_times = second_times = 0
    for num, times in times_dict.items():
        if times > mode_times:
            mode = num
            mode_times = times
        elif times == mode_times:
            second_times = times
    return -1 if mode_times == second_times else mode

if num not in times_dict: times_dict[num] = 0 는 이해하기 쉽고, 
times_dict.setdefault(num, 0) 는 깔끔합니다. 

def solution(array):
    times_dict = {}
    for num in array:
        times_dict.setdefault(num, 0)  #
        times_dict[num] += 1
    mode = -1
    mode_times = second_times = 0
    for num, times in times_dict.items():
        if times > mode_times:
            mode = num
            mode_times = times
        elif times == mode_times:
            second_times = times
    return -1 if mode_times == second_times else mode

sort를 이용해 보았습니다.
sort를 이용하기 위해 key, value를 뒤집어서 새로운 리스트를 만들었죠. 

def solution(array):
    times_dict = {}
    for num in array:
        times_dict.setdefault(num, 0)
        times_dict[num] += 1
    times_list = []  #
    for key, value in times_dict.items():  #
        times_list.append((value, key))  #
    times_list.sort(reverse=True)  #
    if len(times_list) > 1:
        return times_list[0][1] if times_list[0][0] != times_list[1][0] else -1
    return times_list[0][1]

sort와 sorted의 차이를 아시나요? 
a라는 리스트가 있다면 '리스트의 sort 메소드' 즉 a.sort()는 a자체를 정렬합니다.
자체를 정렬하고 끝이기 때문에 None를 반환합니다. 
파이썬에는 sorted라는 내장 함수(BIF)가 있는데요.
sorted(a)는 a자체는 바뀌지 않고 복사 + 정렬된 새로운 리스트를 반환합니다. 

	메소드 / 함수	사용법	작동	리턴값
sort	리스트의 메소드	a.sort()	a 자체를 정렬	None
sorted	파이썬 내장 함수	sorted(a)	정렬된 새 리스트를 만듬	새 리스트

새로운 리스트를 만드는 sorted가 조금 더 느릴 수 있습니다만,
코드를 줄이기 쉽기 때문에 코테에서는 sorted를 더 많이 사용합니다. (개인적인 취향입니다)

def solution(array):
    times_dict = {}
    for num in array:
        times_dict.setdefault(num, 0)
        times_dict[num] += 1
    times_list = sorted(((value, key) for key, value in times_dict.items()), reverse=True)  #
    if len(times_list) > 1:
        return times_list[0][1] if times_list[0][0] != times_list[1][0] else -1
    return times_list[0][1]

뒤집지 않고도 가능한데.. 람다나 operator.itemgetter를 이용하면 됩니다. 

def solution(array):
    times_dict = {}
    for num in array:
        times_dict.setdefault(num, 0)
        times_dict[num] += 1
    times_list = sorted(times_dict.items(), key=lambda x: x[1], reverse=True)
    if len(times_list) > 1:
        return times_list[0][0] if times_list[0][1] != times_list[1][1] else -1
    return times_list[0][0]

람다보다는 itemgetter가 더 빠르기 때문에
실무에서는 itemgetter를 쓰는 것이 좋습니다만,
코테에서는 간결한 람다를 선호합니다.  
https://stackoverflow.com/questions/17243620/operator-itemgetter-or-lambda

 

3. 'collections.Counter'

https://www.daleseo.com/python-collections-counter/

https://docs.python.org/ko/3/library/collections.html

카운터는 딕셔너리가 정석이다 보니
파이썬 3.1부터는 카운터용 유사 딕셔너리를
표준 라이브러리로 제공합니다. 

공식 문서를 보면 3.2, 3.7, 3.10에도 변경사항이 있습니다. 
자주 업데이트 되는 걸 보면 많이 쓰나 봅니다. 

most_common을 이용하면...
정렬까지 한 번에 되기 때문에
깔끔합니다. 

def solution(array):
    from collections import Counter
    counter = Counter(array).most_common()
    if len(counter) > 1:
        return -1 if counter[0][1] == counter[1][1] else counter[0][0]
    return counter[0][0]

 

코틀린

class Solution {
    fun solution(numbers: IntArray): Int {
        val counter = mutableMapOf<Int, Int>()
        for (num in numbers) {
            counter.putIfAbsent(num, 0)
            counter[num] = counter[num]!! + 1
        }
        var (mode, mode_times, second_times) = Triple(-1, 0, 0)
        for ((num, times) in counter.entries) {
            if (times > mode_times) {
                mode = num
                mode_times = times
            } else if (times == mode_times) {
                second_times = times
            }
        }
        return if (mode_times == second_times) -1 else mode
    }
}

코틀린에서 !!는 냄새나는 (좋지 않은) 코드입니다.
엘비스 연산자를 이용하는 것이 추천됩니다. 

class Solution {
    fun solution(numbers: IntArray): Int {
        val counter = mutableMapOf<Int, Int>()
        for (num in numbers) {
            counter[num] = (counter[num] ?: 0) + 1
        }
        var (mode, mode_times, second_times) = Triple(-1, 0, 0)
        for ((num, times) in counter.entries) {
            if (times > mode_times) {
                mode = num
                mode_times = times
            } else if (times == mode_times) {
                second_times = times
            }
        }
        return if (mode_times == second_times) -1 else mode
    }
}

class Solution {
    fun solution(numbers: IntArray) = numbers
        .groupBy { it }
        .map { it.value.size to it.key }
        .sortedByDescending { it.first }
        .let {
            when {
                it.size == 1 -> it.first().second
                it[0].first == it[1].first -> -1
                else -> it.first().second
            }
        }
}