문제 정의
정수 리스트에서 각 정수가 몇 번 등장했는지 딕셔너리로 반환한다. 입력은 정수로만 구성되며, 빈 리스트는 빈 딕셔너리를 반환한다. 입력 리스트는 변경하지 않는다.
입력: [3, 1, 3, 2, 1, 3]
반환: {3: 3, 1: 2, 2: 1}이 문제는 특정 값 하나의 개수를 구하는 문제와 다르다. 서로 다른 값마다 별도의 누적 횟수가 필요하다.
구현
def count_values(numbers):
counts = {}
for number in numbers:
counts[number] = counts.get(number, 0) + 1
return counts
print(count_values([3, 1, 3, 2, 1, 3]))
print(count_values([]))
print(count_values([0, -1, 0])){3: 3, 1: 2, 2: 1}
{}
{0: 2, -1: 1}처음 등장한 정수는 기존 횟수를 0으로 보고 1을 저장한다. 이미 등장한 정수는 저장된 횟수에 1을 더한다. get()만 호출하는 것으로는 저장되지 않으므로 왼쪽의 대입이 필요하다.
반복문이 유지해야 하는 조건
리스트의 앞에서 k개 원소를 처리한 시점에는, counts가 그 k개 원소의 등장 횟수를 정확하게 담고 있어야 한다.
| 처리한 값 | 누적 결과 |
|---|---|
| 3 | {3: 1} |
| 1 | {3: 1, 1: 1} |
| 3 | {3: 2, 1: 1} |
다음 원소에 해당하는 횟수만 1 증가시키므로 이 조건이 유지된다. 반복문이 끝나면 전체 입력의 빈도표가 된다. return을 반복문 안에 두면 첫 원소만 처리하고 종료하므로 위치에도 주의한다.
검증할 사례
assert count_values([]) == {}
assert count_values([7]) == {7: 1}
assert count_values([4, 4, 4]) == {4: 3}
assert count_values([0, -1, 0]) == {0: 2, -1: 1}
original = [3, 1, 3, 2, 1, 3]
before = original.copy()
result = count_values(original)
assert original == before
assert sum(result.values()) == len(original)
assert set(result) == set(original)모든 횟수의 합은 입력 길이와 같아야 한다. 다만 합만 같다고 정답은 아니다. 다른 값의 횟수를 잘못 늘려도 합은 유지될 수 있으므로, 구체적인 기대값 비교도 함께 필요하다.
복잡도와 출력 순서
입력 길이를 n, 서로 다른 정수의 개수를 k라고 하자. 딕셔너리 조회와 갱신을 평균 O(1)로 보면 전체 시간은 평균 O(n), 결과 저장 공간은 O(k)다. 해시 충돌 등에 따른 최악의 경우까지 항상 O(n)이라고 단정하지는 않는다.
정수 크기순 출력이 필요하다면 빈도표를 만든 뒤 키를 정렬한다. 정렬에는 추가로 O(k log k)가 든다. 빈도 집계와 출력 순서 결정은 별도의 요구사항이다.
정리
핵심은 값 → 누적 횟수라는 대응 관계다. 중복을 없애는 집합만으로는 횟수를 보존할 수 없다. 무엇을 기억해야 하는지 먼저 정하면 필요한 자료구조도 분명해진다.
참고
