백준 #2108 - [S3] 통계학 : 최빈값

(python3)

2108번: 통계학

 

 

 

아이디어 : 최빈값 구하기, key 파라미터로 커스텀한 기준으로 sort 하기

가장 직관적인 풀이로 접근했습니다.

평균값, 범위는 max, min, len 으로 쉽게 해결이 가능하고, median 도 sort 해서 가운데값을 찾아주면 됩니다.

최빈값이 문젠데, 최빈값은 여러개일 경우에 두번째로 작은 값을 찾아야하는 커스텀한 기준이 있으므로 이걸 잘 반영해줘야합니다. 제일 쉬운 방법은 각 수와 카운트값을 저장해서 카운트값 기준 내림차순, 수 기준 오름차순으로 정렬해주고, 최빈값이 2개 이상이면 두번째 값을 찾아주는 것입니다. 

파이썬에서 제공하는 기본 sort, sorted 메서드에서 사용되는 방식이 timsort 이기 때문에 시간복잡도는 O(NlogN) 이 됩니다.

key 파라미터로 커스텀한 기준으로 sort 하는 방법은 아래 글에 작성해뒀습니다.

[sort] 파이썬에서 커스텀한 기준으로 이터러블한 객체 정렬하기

 

 

코드

def solution(input) : 
    # 입력받기
    N = int(input().strip())
    nlist = []
    for _ in range(N) :
        nlist.append(int(input().strip()))

    mean, median, most_custom, tigerup = 0,0,0,0 # 변수 설정
    nlist.sort()
    mean = round(sum(nlist) / N)
    median = nlist[N//2]

    # 커스텀 최빈값 구하기
    cnt = 1
    num = nlist[0]
    most = [] # nlist 배열을 (값, 횟수)] 의 배열로 표현을 치환 = most
    for i in nlist[1:] :
        if num != i :
            most.append((num,cnt))
            num = i
            cnt = 1
        else :
            cnt+=1
    most.append((num,cnt))

    most.sort(key = lambda x : (x[1]*-1,x[0])) # 횟수 기준 내림차순, 값 기준 오름차순으로 정렬

    # 최빈값이 여러개일대 두 번째로 작은 값 출력
    if len(most) > 1 and most[0][1] == most[1][1] :
        most_custom = most[1][0]
    else : most_custom = most[0][0]

    # 범위 계산
    tigerup = max(nlist) - min(nlist)

    print(mean)
    print(median)
    print(most_custom)
    print(tigerup)

solution(input)

 

 

최단 시간 코드 분석

이번에는 해당 문제의 최단 시간 코드도 한번 분석해보려고 합니다.

제 코드는 484ms, 공개된 코드 중 최단 시간 코드는 176ms 입니다. 세상엔 역시 똑똑한 사람이 많고 그만큼 배울것도 많네요.

참고한 코드 출처 : https://www.acmicpc.net/source/37033270

 

이 코드의 경우 sort 를 한번도 사용하지 않고도 sort 된 형태를 만드는 방식으로 구현했습니다. 배열도 딱 한번 돌면서 모든 요소들을 계산하면서 시간이 또 단축되네요. 자세한 사항은 줄마다 주석으로 넣었습니다. O(N) 으로 해결됩니다.

from sys import stdin


def sol2108():
    n = int(stdin.readline())
    counts = [0]*8001 # 입력되는 정수가 -4000~4000 으로 주어지므로 각 정수의 count 값을 저장하는 배열로 치환
    s = 0 # sum
    for i in stdin:
        num = int(i)
        counts[num+4000] += 1

    maxc = max(counts) # 최빈값의 횟수
    mode = mcnt = 0 # 최빈값, 몇번째 최빈값인지
    idx = 0 
    med = None
    mi, ma = 4001, -4001
    for i in range(8001): # 이렇게 탐색하면 가장 작은 수 부터 오름차순으로 탐색하는 꼴
        cnt = counts[i]
        if cnt == 0: # 등장한적 없는 수 면 넘어가기
            continue

        num = i-4000 # 실제 값으로 변경
        s += num*counts[i] # sum 에 더하기
        if cnt == maxc and mcnt < 2: # 최빈값 중 하나고, 최빈값이 1개면 1번째, 2개 이상이면 2번째로 작은 최빈값으로 저장됨.
            mode = num
            mcnt += 1
        mi = min(mi, num) # 최소
        ma = max(ma, num) # 최대
        
        # 여기부턴 중앙값 구하기. 중앙값은 정렬된 수열에서 인덱스가 정해져있음.
        # 지금 데이터가 저장된 방식은 애초에 오름차순 정렬되어 있다고 보면 됨.
        # 이 경우는 idx가 배열의 인덱스가 아니라 몇번째 숫자인지를 세어야하기 떄문에 1부터 시작
        # 고로 중앙값 idx = N//2 + 1 이 됨.
        idx += counts[i]
        if idx >= n//2+1 and med == None: # 중앙값이 되는 수가 여러번 등장하는 경우 idx 가 딱 중앙값에서 끝나지 않을 수 있음. 그래서 크거나 같다로 처리. 처음으로 중앙값 인덱스를 넘어가는 순간의 값이 우리가 찾는 중앙값임.
            med = num

    print(round(s/n), med, mode, ma-mi, sep='\n') # sep 파라미터를 사용해서 한번에 출력


if __name__ == '__main__':
    sol2108()

 

 

my solved.ac :

solved.ac