[프로그래머스] 120812: 최빈값

안녕하세요.

이번 문제는 프로그래머스의 120812번 입니다.

최빈값을 구하는 문제입니다. 

 

문제

 

코드

def solution(array):
    d=dict()
    r=[]
    
    for i in range(len(array)):
        v = array[i]
        
        if v in d: d[v] = d[v] + 1
        else: d[v] = 1
            
        if len(r) > 0:
            if v in r or d[r[len(r)-1]] < d[v]:
                r=[v]
            elif v not in r and d[r[len(r)-1]] == d[v]: 
                r.append(v)
        else:
            r=[v]
            
    return -1 if len(r) > 1 else r[len(r)-1]

 

알고리즘 캔버스

아이디어

1. 각 값마다의 빈도를 저장하는 dict(이하 d)와 현재 최빈값을 저장하는 array(이하 r)를 선언한다.
2. array의 길이만큼 순회한다.
3. 순회하며 d에 [값]: 갯수 형태로 빈도수를 저장한다.
   1. 이미 키가 존재한다면 +1 시키고,
   2. 키가 존재하지 않는다면 1로 초기화시킨다.
4. 순회하며 r에 현재 기준 최빈값을 저장한다.
   1. 최빈값이 아직 하나도 없다면(len이 0 이라면), 현재 값을 최빈값으로 지정한다.
   2. 이미 최빈값이 존재하고, 그 최빈값 안에 현재 요소가 존재한다면
      1. 기존 최빈값들보다 값이 커진것이므로 r을 초기화하고 현재 값을 최빈값으로 지정한다.
   3. 이미 최빈값이 존재하고, 그 값에 현재 요소가 포함되지 않고, 최빈 값 중 랜덤한 하나의 값이 현재 요소의 빈도와 같다면
      1. r에 현재 요소를 추가한다.
5. 순회가 끝나고 최종적으로 r의 갯수가 1보다 크다면 -1을 리턴하고, 아니라면 0번을 리턴한다.

시간 복잡도 (Big-O)

- O(N)

 

테스트 케이스 

다른 사람의 풀이

- 이번 문제의 경우는 Collections의 Counter를 사용해서 비교적 간단히 풀이한 분들도 계셨습니다.

  - 효율적이고 가독성이 좋은 풀이입니다.

- 또한, 임의의 크기 배열을 만든 이후 해당 배열에 최빈값을 구하고, 이후 배열의 최대 값을 구해 값을 리턴하는 풀이도 있었습니다. 

  - 이 접근도 좋은 것 같습니다. 

 

 

감사합니다.