https://www.acmicpc.net/problem/2108
문제 요약
정수 N을 입력받고 (단 N은 홀수)
1. 산술평균 (소수점 이하 첫째 자리에서 반올림)
2. 중앙값
3. 최빈값
4. 범위
를 출력하는 문제.
접근 방법
1. 산술평균 (Arithmetic Mean)
- 모든 수의 합을 수의 개수로 나눈 값.
- 소수점 첫째 자리에서 반올림해야 함.
- 파이썬에서는
round()함수 사용 가능.
avg = round(sum(numbers) / len(numbers))2. 중앙값 (Median)
- 정렬된 리스트에서 가운데 있는 값.
- N이 홀수이므로 인덱스로 바로 접근 가능.
sorted_numbers = sorted(numbers)
median = sorted_numbers[len(numbers) // 2]3. 최빈값 (Mode)
- 가장 자주 등장한 값.
- 여러 개면 두 번째로 작은 값을 출력해야 함.
collections.Counter를 활용하면 빈도 계산이 편리함.
from collections import Counter
counter = Counter(numbers)
most_common = counter.most_common()
max_freq = most_common[0][1]
modes = [num for num, freq in most_common if freq == max_freq]
modes.sort()
mode = modes[0] if len(modes) == 1 else modes[1]그런데 나는 라이브러리를 쓰고 싶지 않았다.
자료구조 속 개수를 셀 때는 리스트 말고 딕셔너리를 쓰면 좋다고 한다.
🧠 최빈값을 구할 때 리스트 대신 딕셔너리를 사용하는 이유
통계 문제에서는 어떤 수가 가장 자주 등장했는지, 즉 최빈값을 구해야 하는 경우가 많다.
이때 리스트만 가지고 해결하려 하면 시간 초과가 날 수 있다.
❌ 리스트만 사용할 때의 문제점
max_freq = 0
for num in numbers:
freq = numbers.count(num) # O(N)
max_freq = max(max_freq, freq)numbers.count(x)는 리스트 전체를 순회하며x의 개수를 세기 때문에 O(N)- 이걸 모든 숫자에 대해 반복하면 최악의 경우 O(N²) 로 시간초과 발생 💥
✅ 딕셔너리를 사용한 해결 방식
딕셔너리는 key: value 형태로 값을 저장한다.
→ 여기서 key는 숫자, value는 그 숫자의 등장 횟수로 사용하면 된다.
freq = {}
for num in numbers:
if num in freq:
freq[num] += 1
else:
freq[num] = 1이렇게 하면 리스트를 한 번만 순회하면서 등장 횟수를 모두 기록할 수 있다.
⚙ 딕셔너리는 왜 빠를까? (해시테이블 원리)
딕셔너리는 해시테이블(Hash Table) 이라는 자료구조 기반으로 동작한다.
- key(예: 숫자 2)를 해시 함수에 넣는다 → 고유한 숫자(hash값)를 반환
- 이 숫자를 배열의 인덱스로 사용해 저장하거나 꺼냄
hash(2) → 834712 → 인덱스 위치 계산 → 바로 접근즉, 순회하지 않고도 바로 위치를 계산해서 데이터를 찾거나 저장할 수 있다.
⏱ 시간복잡도 비교
| 작업 | 리스트 | 딕셔너리 |
|---|---|---|
| 값 추가 | O(1) | O(1) |
값 조회 (count) | O(N) | O(1) |
| 전체 빈도 계산 | O(N²) | O(N) |
딕셔너리는 숫자 하나하나를 읽으면서 등장 횟수를 기록하고,
필요할 때는 계산 없이 바로 꺼내볼 수 있다.
🔍 결론
- 최빈값을 구할 때는 리스트보다 딕셔너리가 훨씬 효율적이다.
- 딕셔너리는 해시테이블 기반으로, 값을 빠르게 저장하고 조회할 수 있다.
- 시간복잡도는 리스트보다 훨씬 낮아 시간 초과를 방지할 수 있다.
📌 요약 예시 코드
freq = {}
for num in numbers:
if num in freq:
freq[num] += 1
else:
freq[num] = 1
max_freq = max(freq.values())
modes = [num for num, cnt in freq.items() if cnt == max_freq]
modes.sort()
mode = modes[0] if len(modes) == 1 else modes[1]4. 범위 (Range)
- 최댓값과 최솟값의 차이.
range_val = max(numbers) - min(numbers)내 해답
import sys
N = int(sys.stdin.readline())
numbers = []
for _ in range(N):
numbers.append(int(sys.stdin.readline().strip()))
avg = round(sum(numbers) / N)
median = sorted(numbers)[N // 2]
range_ = max(numbers) - min(numbers) # range 가 파이썬 내장함수라서 range_로 선언
freq = {}
for num in numbers:
if num in freq:
freq[num] += 1
else:
freq[num] = 1
# 최빈값 처리
max_freq = max(freq.values())
modes = [num for num, count in freq.items() if count == max_freq] #count가 max_freq인 숫자(num)만 모아 리스트로 만들기!
modes.sort()
mode = modes[0] if len(modes) == 1 else modes[1]
print(avg)
print(median)
print(mode)
print(range_)배운 기술
modes = [num for num, count in freq.items() if count == max_freq]dictionary.items()
freq.items()는 딕셔너리의(key, value)쌍을 반환한다.
→ 여기서key는 등장한 숫자,value는 등장 횟수이다.for num, count in freq.items()는 각각의 숫자와 그 횟수를 받아오는 튜플 언패킹 문법이다.
-> num,count 라는 변수에 key,value 가 담긴다.
파이썬 삼항 연산자
mode = modes[0] if len(modes) == 1 else modes[1]- 파이썬의 조건부 표현식(삼항 연산자) 문법이다.
- 구조는 다음과 같다:
<조건이 참일 때 값> if <조건> else <조건이 거짓일 때 값>- 위 코드는 다음과 같은 의미이다:
modes의 길이가 1이면 →modes[0]을mode에 저장- 아니면 (여러 개면) →
modes[1]을mode에 저장
Frontend Engineers