문제 정의: 최빈값이 여러 개라면 무엇을 반환할까
정수 리스트에서 가장 많이 등장한 값을 반환한다. 최빈값이 여러 개라면 가장 작은 정수를 선택하고, 빈 리스트라면 None을 반환한다. 입력 리스트는 변경하지 않는다.
이 글의 동률 규칙은 직접 만든 연습 문제의 조건이다. 다른 문제에서는 첫 등장 값이나 모든 최빈값을 요구할 수 있으므로 그대로 적용하면 안 된다.
[4, 2, 4, 2, 7] → 2
[3, 3, 1] → 3
[] → None빈도표와 후보 선택을 분리한다
def smallest_mode(numbers):
counts = {}
for number in numbers:
counts[number] = counts.get(number, 0) + 1
best_value = None
best_count = 0
for value, count in counts.items():
if (best_value is None
or count > best_count
or (count == best_count and value < best_value)):
best_value = value
best_count = count
return best_value
print(smallest_mode([4, 2, 4, 2, 7]))
print(smallest_mode([3, 3, 1]))
print(smallest_mode([]))2
3
None첫 반복문은 값별 등장 횟수를 만든다. 두 번째 반복문은 현재까지 확인한 값 중 가장 좋은 후보를 유지한다. 더 많이 등장한 값이면 교체하고, 횟수가 같으면 더 작은 값으로 교체한다.
best_value is None은 아직 후보가 없음을 의미한다. 입력은 정수로 제한했으므로 실제 값과 구분된다. 또한 or는 앞 조건이 참이면 뒤 조건을 평가하지 않으므로 첫 후보에서 정수와 None을 크기 비교하지 않는다.
횟수만 비교하면 입력 순서에 끌려간다
[4, 2, 4, 2, 7]의 빈도표에서 4와 2의 횟수는 모두 2다. 후보 교체 조건을 count > best_count만으로 두면 먼저 확인한 4가 남는다. 요구한 답은 2이므로 동률 조건이 반드시 필요하다.
반대로 단순히 >=로 바꾸면 마지막에 확인한 동률 후보가 선택된다. 이것도 “가장 작은 값”이라는 조건과 다르다. 비교 연산자 하나를 바꾸는 것으로 문제의 규칙을 대신할 수는 없다.
경계값과 입력 순서 검증
assert smallest_mode([]) is None
assert smallest_mode([0]) == 0
assert smallest_mode([-2, -1, -2, -1]) == -2
assert smallest_mode([5, 3, 1]) == 1
assert smallest_mode([8, 8, 2]) == 8
assert smallest_mode([4, 2, 4, 2, 7]) == 2
assert smallest_mode([7, 2, 4, 2, 4]) == 2
numbers = [4, 2, 4, 2, 7]
before = numbers.copy()
smallest_mode(numbers)
assert numbers == before이 문제의 정답은 값별 횟수와 대소 관계로 결정된다. 같은 원소들의 순서만 바꾸어도 정답은 같아야 한다. 0이나 음수를 포함한 사례는 초기값을 임의의 정수로 두었을 때 생기는 오류를 확인하는 데 유용하다.
복잡도
입력 길이를 n, 서로 다른 정수 수를 k라고 하면 빈도표 생성은 평균 O(n), 후보 탐색은 O(k)다. 딕셔너리 연산을 평균 O(1)로 보는 조건에서 전체 평균 시간은 O(n), 추가 공간은 O(k)다. 최빈값 하나만 필요하므로 모든 후보를 정렬할 필요는 없다.
함께 보기
