[실버 3] 2108번: 통계학

Original Source: https://www.acmicpc.net/problem/2108

2108번: 통계학

---

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

---

사고의 흐름

• 중앙값을 구하려면 정렬을 해야겠다. 일단 리스트로 숫자를 모두 받고 정렬을 한 다음 각각의 통계값을 구하면 될 듯?
• 확실히 정렬을 먼저 한 다음 통계값을 계산하는 게 중앙값과 범위를 도출하기에 편하겠다.
• N이 500,000개까지 주어지므로 시간 복잡도는 O(NlogN) 미만이여야 한다. 이중 반복문을 사용할 수는 없겠네?
• 최빈값을 구하기가 어려워 보인다...숫자와 숫자가 나온 횟수를 전부 저장해야 하나?
• 정렬을 수행하는 과정에서 모든 숫자를 한번씩 읽어야 하니까 그 때 데이터를 저장하면 될 것 같긴 한데...
• 만약 count 리스트를 따로 만들어서 정렬을 수행하면서 데이터를 저장한다고 쳐도, 결국 다시 정렬해서 두 번째로 작은 값을 구해야 하는데, 그러면 시간 복잡도가 너무 커진다.
• 유용하게 사용할 수 있는 다른 자료형을 한번 찾아볼까?
• 사전 자료형은 데이터의 조회 및 수정이 O(1)만에 가능하니 시간 복잡도를 줄일 수 있지 않을까? 숫자와 숫자가 나타난 횟수를 Key와 Value 쌍으로 묶어서 저장하면 깔끔하겠는데?
• input을 받을 때 들어온 숫자와 일치하는 Key값이 존재하면 그 Key값의 Value를 증가시키고, 존재하지 않으면 새로운 Key값을 추가한 뒤 Value를 1 올리면 되겠다.
• 이중 반복문을 못 쓴다 뿐이지, 반복문 자체는 여러 번 돌려도 되지 않을까? 그러면 우선 Key값을 기준으로 정렬시키면서 산술평균, 중앙값, 범위를 구하고, Value값을 기준으로 다시 정렬시키면서 최빈값을 구해야겠다. 일단 해 보고 시간초과 나는지 확인해봐야겠다.

 

• 중앙값을 구하려면 input을 받을 때 숫자가 중첩되면 안 된다. 이러면 사전 자료형 못 쓰지...그냥 리스트를 쓰는 쪽으로 방향을 선회해야겠다.
• 사전 자료형은 숫자의 개수를 카운팅할 때 쓰면 되겠네. Key를 숫자, Value를 숫자가 나온 횟수로.
• 사전을 Value 기준으로 정렬하는 게 좀 부자연스럽다고 느껴지는데, 다른 좋은 방법이 없을까?
• 사전을 정렬할 필요 없이 Value, 즉 카운트 횟수가 가장 큰 데이터 쌍만 추출해서 리스트로 만든 다음 정렬해서 답을 구하면 되겠다!
• 이전에 이미 다른 통계값을 구하기 위해 Input을 저장한 리스트를 한 번 정렬해 놓았으니, 정렬된 리스트를 이용해서 사전을 만들면 카운트 횟수를 추출한 리스트를 정렬한 필요가 없겠네!

 

• 제출해 보니 런타임 에러가 뜨네...원인을 모르겠으니 특수한 테스트 케이스 위주로 테스트하면서 원인을 찾아보자.
• IndexError면 정해진 배열의 크기 바깥에서 인덱싱을 시도했다는 이야기인데, 반복문을 돌다가 인덱스가 배열 크기 바깥으로 벗어나는 경우가 많으니 아마도 반복문 주변에 버그가 있나 보다.
• 반복문 이전의 코드만 제출해서 런타임 에러가 뜨는지 확인해보자. 만약 런타임 에러가 뜨지 않으면 반복문에 버그가 있는 게 확실하다.

 

• 반복문 이전의 코드만 제출해봤는데 런타임 에러가 뜨네? 생각 외로 중앙값을 가져오는 부분에 오류가 있었다.
• 그런데 내가 작성한 부분을 보면 배열 크기의 바깥으로 인덱스가 나갈 이유가 없는데? 내가 알지 못하는 부분에 버그가 있나?
• 다른 정답자와 소스코드를 비교해 보니 Input을 받는 부분이 달랐다. 나는 input().split() 메서드를 사용해서 Input을 받았는데, 그 사람은 for문과 .append()를 써서 들어오는 Input을 하나하나 리스트에 집어넣고 있었다. 그래서 문제를 다시 보니 Input이 공백을 기준으로 분리되지 않고 한 줄에 하나씩 분리되어 있었다. 이게 문제인가?
• 그 사람처럼 Input을 .append() 메서드로 받아보니 런타임 에러가 사라졌다!
• 다른 백준 문제들은 input().split()으로 해도 됐었는데, 그건 운이었나? 어쨌든 문제에 Input이 공백 기준으로 분리되었다고 명시되지 않았으니 .append() 메서드로 하나하나 리스트에 집어넣는 게 옳은 방법인 것 같다.

내가 작성한 소스코드

# 시간 초과

n = int(input())
numbers = []
for _ in range(n):
    numbers.append(int(input()))

mean = int(round(sum(numbers) / n, 0))

numbersSorted = sorted(numbers)

median = numbersSorted[n // 2]
scope = numbersSorted[-1] - numbersSorted[0]

cnt = {}

for i in range(n):
    if numbersSorted[i] in cnt:
        cnt[numbersSorted[i]] += 1
    else:
        cnt[numbersSorted[i]] = 1

cntKeys = list(cnt.keys())
cntMax = 0
modeList = []

for i in range(len(cnt)):
    if cntMax < cnt[cntKeys[i]]:
        cntMax = cnt[cntKeys[i]]

for i in range(len(cnt)):
    if cnt[cntKeys[i]] == cntMax:
        modeList.append(cntKeys[i])

mode = 0;
if len(modeList) < 2:
    mode = modeList[0]
else:
    mode = modeList[1]
        
print(mean)
print(median)
print(mode)
print(scope)

남이 작성한 소스코드

Jiwon_C 님:
https://jiwon-coding.tistory.com/8

[백준] 2108번 통계학 파이썬(python)

피드백

• 아직 초보니까 어줍잖게 시간 복잡도부터 고려하지 말고, 일단 돌아가는 로직을 설계하는 데 중점을 맞추자. 제출한 뒤 시간 초과가 뜨면 그때 수정해도 늦지 않다.
• 시간 복잡도는 차수가 가장 큰 항만 고려하고 나머지는 버린다. 그러므로 사전 자료형을 써서 데이터 탐색의 시간 복잡도를 O(1)으로 낮춘다고 한들 전체 프로그램의 시간 복잡도가 줄어드는 것은 아니다.
• 예약어를 변수 이름으로 사용하지 말자(count -> cnt, sum -> total).
• Input이 어떤 방식으로 들어오는지도 살펴야 한다. 만약 Input이 공백 기준으로 분리되지 않았으면 반복문 내부에 .append() 메서드를 써서 Input을 받는 것이 안전하다.
• 시간 초과를 방지하기 위해 파이썬 기본 메서드 대신 sys.stdin.readline() 메서드를 사용하자.
• 등장 횟수를 카운팅할 때는 collections 모듈의 Counter 클래스를 사용하면 편리하다.
• 적당히 고민해보되, 고민해도 모르겠으면 혼자 싸매지 말고 정답자의 소스코드를 찾아가서 내 코드와 차이점을 비교하자. 시간도 자원이니만큼 한 문제 한 문제에 너무 많은 시간을 투자할 필요는 없다.