코딩테스트 21일차(2025.02.11) - 백준2108번(통계학)

문제유형

구현, 수학, 시간복잡도

풀이 방법 도출 과정

1. 문제를 보고 간단하게 값들을 리스트하고 파이썬 내장함수를 사용하고자 함.

2. 하지만 이 방법으로 풀었을 시 시간초과가 발생, 이것은 시간복잡도의 문제임

3. 가장 먼저 첫번째 받는 값을 이미 만들어진 인덱스값을 사용하도록 한다. 이건 for문을 사용하지 않는 방법이다.

4. 첫번째를 제외한 N번째 수의 경우 입력을 받고 저장한 다음에 그 내용을 보여주는 것이 아닌 입력을 받으면서 합계, 최솟값, 최댓값, 빈도수를 동시에 계산하기 위한 방법을 사용한다.

5. 산술 평균은 모든 수의 합을 total에 누적시키며, 마지막에 total / N을 구하여 계산합니다. 입력받을 때마다 total을 갱신하고, 결과적으로 전체 합을 구할 수 있다.

6. 중앙값은 오름차순으로 정렬된 상태에서 가운데 값을 구하지 않고 정렬을 하면 시간복잡도가 증가하기 때문에 빈도수를 기반으로 빠르게 중앙값을 찾는다. counts 배열을 이용하여 누적 빈도를 계산하면서 N//2를 넘는 첫 번째 값을 찾아 중앙값을 구한다.

7. 최빈값은 counts 배열을 순차적으로 확인하여 최대 빈도수와 그에 해당하는 값들을 찾고, 여러 값이 있을 경우 두 번째로 작은 값을 선택하여 답을 구한다.

8. 범위는 주어진 수 중에서 최댓값과 최솟값의 차이이기 때문에 이를 생각하여 간단하게 최솟값과 최댓값을 빼주면 된다. 

시간 복잡도

 

• 입력 처리 및 값 계산: O(N)
• 산술 평균 계산: O(1)
• 중앙값 계산: O(1) (상수 시간)
• 최빈값 계산: O(1) (상수 시간)
• 범위 계산: O(1)
• 그러므로 총 O(N)이 전체 시간 복잡도이다.

 

코드 및 간단설명

입력값의 범위가 미리 정해져 있어, 이를 기반으로 데이터를 실시간으로 처리하고 결과를 즉시 계산하여 출력하는 방식으로 시간 복잡도를 최적화하였다.

import sys

input = sys.stdin.readline

N = int(input())
# 값의 범위가 -4000 ~ 4000 이므로 총 8001개의 인덱스를 사용
counts = [0] * 8001  
total = 0
min_val = 4001
max_val = -4001

# 입력을 받으면서 합계, 최솟값, 최댓값, 빈도수를 동시에 계산
for _ in range(N):
    num = int(input())
    total += num
    counts[num + 4000] += 1
    if num < min_val:
        min_val = num
    if num > max_val:
        max_val = num

# 1. 산술평균 (소수 첫째 자리에서 반올림)
mean = int(round(total / N))
print(mean)

# 2. 중앙값
# 누적 빈도수(cumulative frequency)를 이용하여 중앙값 위치(1-indexed: N//2 + 1)를 찾음
count_sum = 0
median = None
for idx in range(8001):
    count_sum += counts[idx]
    if count_sum >= (N // 2) + 1:
        median = idx - 4000  # 인덱스를 실제 값으로 변환
        break
print(median)

# 3. 최빈값
max_freq = max(counts)
mode_list = []
# 고정된 범위(8001) 내에서 최대 빈도와 같은 값을 가진 수들을 찾음
for idx, cnt in enumerate(counts):
    if cnt == max_freq:
        mode_list.append(idx - 4000)
# 후보가 여러 개일 경우 두 번째로 작은 값을 선택
if len(mode_list) > 1:
    mode_list.sort()
    mode = mode_list[1]
else:
    mode = mode_list[0]
print(mode)

# 4. 범위
range_val = max_val - min_val
print(range_val)

입력값의 범위가 미리 정해져 있어, 이를 기반으로 데이터를 실시간으로 처리하고 결과를 즉시 계산하여 출력하는 방식으로 시간 복잡도를 최적화하였다.