중첩 반복문으로 개수를 세는 O(n²) 풀이를 해시 기반 O(n) 풀이로 바꾸는 대표 문제입니다. 코딩 테스트의 빈도·통계 문제 대부분에 재사용됩니다.
정수 리스트의 각 값이 몇 번 등장하는지 dict로 반환하세요. 키는 원소, 값은 등장 횟수입니다.
count_frequencies(numbers)
평균 시간 O(n), 공간 O(k) — k는 서로 다른 값의 수
실행하면 아래 순서대로 채점합니다. print() 출력도 이 순서대로 쌓입니다.
| # | 이름 | numbers | 기대값 |
|---|---|---|---|
| 1 | 여러 중복 | [1, 2, 1, 3, 2, 1] | {1: 3, 2: 2, 3: 1} |
| 2 | 음수 포함 | [-1, -1, 0] | {0: 1, -1: 2} |
| 3 | 빈 리스트 | [] | {} |
| 4 | 모두 서로 다름 | [4, 1, 9] | {1: 1, 4: 1, 9: 1} |
| 5 | 모두 같은 값 | [6, 6, 6, 6] | {6: 4} |
Python 표준 라이브러리는 사용할 수 있습니다. 함수 이름과 매개변수는 제시된 형태를 유지하세요.
dict / set)dict.get(key, 0)과 set을 익혀두면 중첩 반복을 줄일 수 있습니다.코드를 작성하고 실행하면 5개의 테스트가 각각 표시됩니다.