[알고리즘] 최빈값 구하는 알고리즘 (직접 구현/Counter 클래스로 구하는 법) - Python

오늘은 Python의 인덱스를 이용하여 최빈값을 구하는 법을 알아 보겠습니다. 

numpy의 최빈값을 구해주는 함수 mode를 사용하면 편리하지만, 직접 구할 때는 어떤 로직을 사용해야 하는지 정리해봤고 추가로 자주 쓰인 

 

핵심 로직

핵심 로직은 아래와 같다. 최댓값을 가지는 원소의 크기만큼의 빈 배열을 생성한다고 하였는데, 최댓값이 100일 때 이 크기만큼의 빈 배열을 생성하면, 길이가 100인 빈 리스트가 생성된다. 그리고 이 빈 리스트는 최댓값까지 순차적으로 1~100까지 각 자릿수가 나왔을 때 빈도를 저장하는 역할을 한다. 

1. 최빈값을 구할 리스트 A의 최댓값을 가지는 원소를 구한다.
2. 그 원소의 값만큼의 길이를 가진 빈 배열 B를 생성한다.
3. 빈 배열 B에는 각 자리수의 빈도수가 저장된다.
4. 리스트 A의 각 원소를 반복문을 돌며, 한 원소가 나오면 그 그 원소값으로 빈배열 B를 인덱싱 해서 값을 +1 해준다.
5. 이 과정을 전부 반복하면 빈 배열 B에는 각 자릿수가 나온 빈도만큼의 값이 저장되어 있을 것이다.
6. 이때, 빈 배열 B가 가진 최댓값의 인덱스 +1을 하면, 그 숫자가 최빈값이 된다.

 

주어지는 배열 A의 최댓값이 100이면 1~100까지의 빈 리스트가 생성되고, 생성된 리스트의 각 자리는 해당 자리값의 숫자가 가지는 빈도수를 저장하게 된다.

 

아래 예시를 보면 편하다. 예를 들어 InputList로 아래와 같은 값이 주어지면, InputList의 최댓값이 10이므로 10만큼의 빈 배열 myList를 생성해 준다. 그리고 각 자리는 (인덱스+1) 숫자가 가지는 빈도를 저장한다.

 

그러면 결과적으로 inputList의 각 원소를 모두 반복문을 돌리며 각 자릿수의 인덱스에 +1해 주면 아래 3번째 줄의 결과가 나온다. 주어진 inputList에서 1은 1번, 2는 2번, 3은 0번, 4는 2번, 7은 3번 등등으로 나왔으므로, 이 빈도수 값을 저장한 myList가 최종적으로 도출된다. 그러면 이 myList에 최댓값인 3의 인덱스+1(6+1)을 해주면 주어진 리스트에서 최빈값을 가지는 원소가 7 임을 알 수 있다. 

 

 

 

 

구현 코드

최빈값이 두 개 이상이면 위와 같은 원리로 최빈값이 나오는 인덱스를 따로 또 저장해서, 인덱스의 인덱스를 활용하여 구해주면 풀어주면 된다. 

N=int(input())
target=[]

for i in range(N):
    tmp=int(input())
    target.append(tmp)
# sort에서 reverse True가 내림차순, False가 오름차순으로 디폴트 값 
target.sort() # 오름차순

def mode(target):
    K=int(max(target))
    myList=[0]*K
    modeIndex=[]
    for i in target:
        myList[i-1]+=1
    modeValue=myList.index(max(myList))+1
    print(myList)
    # 최빈값이 두 개 이상이면 [2,0,2,2,1]
    if myList.count(modeValue)>=2: 
        for i in range(len(myList)):
            if myList[i]==modeValue:
                modeIndex.append(i) 
        modeValue=myList[len(modeIndex)-1]+1 # 가장 마지막에 나오는 최빈값
    return modeValue

print(mode(target))

 

 

Reference

• https://geunskoo.github.io/class2++/boj-2108/
• https://joylee-developer.tistory.com/94