사용자 도구

사이트 도구


ps:problems:boj:2108

통계학

ps
링크acmicpc.net/…
출처BOJ
문제 번호2108
문제명통계학
레벨실버 4
분류

기초

시간복잡도O(nlogn)
인풋사이즈n<=500,000
사용한 언어Python
제출기록50552KB / 512ms
최고기록228ms
해결날짜2021/08/24

풀이

  • 산술평균과 범위는 간단하게 O(n)으로 계산 가능하다. 중앙값은 선택 알고리즘을 사용하면 O(n)에 계산이 가능하지만, 보통은 그냥 O(nlogn)으로 정렬한 뒤에 해당 값을 찾는것이 더 빠르다. 최빈값도 정렬을 한 이후라면 쉽게 O(n)에 찾을 수 있고, 각 숫자별 카운팅을 한다면 정렬 없이 그냥 O(n)에 구할수도 있다.
    • 최빈값의 경우는 최빈값이 여러개일 경우 2번째로 작은 값을 출력하라는 조건떄문에 아주 간단하지는 않다.
  • 사실 python에서는 statistics 라이브러리에 이 함수들이 구현되어 있다. (하지만 그냥 구현해도 워낙 간단하다보니 쓸일이 별로 없다). 처음에는 라이브러리 함수들을 이용해서 작성했지만 조금 비효율적인 부분이 많아서, 그냥 라이브러리 안쓰고도 작성해봤다. 후자가 살짝 빨랐다.
  • 정렬 없이 숫자별 카운팅을 해놓고 진행할수도 있다. 최빈값을 쉽게 구할수 있고, 중앙값도 카운트의 누적합이 n/2가 넘어가는 인덱스를 찾으면 되니까 간단하다. 시간복잡도도 O(n)이고 군더더기도 없어서 더 효율적일것 같지만 구현은 안해봤다.

코드

코드 1 - statistics 모듈 사용

"""Solution code for "BOJ 2108. 통계학".

- Problem link: https://www.acmicpc.net/problem/2108
- Solution link: http://www.teferi.net/ps/problems/boj/2108
"""

import statistics
import sys


def main():
    N = int(sys.stdin.readline())
    nums = [int(sys.stdin.readline()) for _ in range(N)]

    print(round(statistics.mean(nums)))
    print(statistics.median(nums))
    modes = statistics.multimode(nums)
    if len(modes) == 1:
        print(modes[0])
    else:
        print(sorted(modes)[1])
    print(max(nums) - min(nums))


if __name__ == '__main__':
    main()

코드 2 - 그냥 직접 정렬해서 구현

"""Solution code for "BOJ 2108. 통계학".

- Problem link: https://www.acmicpc.net/problem/2108
- Solution link: http://www.teferi.net/ps/problems/boj/2108
"""

import itertools
import sys


def main():
    N = int(sys.stdin.readline())
    nums = [int(sys.stdin.readline()) for _ in range(N)]
    nums.sort()
    
    print(round(sum(nums) / N))
    print(nums[N // 2])    
    mode, count, is_first = 0, 0, False
    for k, g in itertools.groupby(nums):
        l = len(list(g))
        if l > count:
            mode, count, is_first = k, l, True
        elif l == count and is_first:
            mode, count, is_first = k, l, False    
    print(mode)    
    print(nums[-1] - nums[0])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
L O᠎ D C D
 
ps/problems/boj/2108.txt · 마지막으로 수정됨: 2021/08/24 14:52 저자 teferi