문제 개요
공장에 번호가 l부터 r까지 매겨진 n개의 공이 있고, 1번부터 무한대까지 번호가 붙은 상자가 무한히 많다고 가정해 봅시다. 각 공은 공 번호의 자릿수 합과 같은 번호의 상자에 넣습니다. 예를 들어 번호가 123인 공은 1 + 2 + 3 = 6이므로 6번 상자에 들어갑니다.
두 값 l과 r이 주어졌을 때, 우리가 구해야 하는 것은 가장 많은 공이 담긴 상자에 들어 있는 공의 개수입니다.
예시
입력이 l = 15, r = 25라면 출력은 2가 됩니다. 그 이유는 다음과 같습니다.
- 15번 공 → 1 + 5 = 6번 상자
- 16번 공 → 1 + 6 = 7번 상자
- 17번 공 → 1 + 7 = 8번 상자
- 18번 공 → 1 + 8 = 9번 상자
- 19번 공 → 1 + 9 = 10번 상자
- 20번 공 → 2 + 0 = 2번 상자
- 21번 공 → 2 + 1 = 3번 상자
- 22번 공 → 2 + 2 = 4번 상자
- 23번 공 → 2 + 3 = 5번 상자
- 24번 공 → 2 + 4 = 6번 상자
- 25번 공 → 2 + 5 = 7번 상자
6번 상자에는 15번, 24번 공이, 7번 상자에는 16번, 25번 공이 들어가 각각 2개씩으로 가장 많습니다. 따라서 정답은 2입니다.
풀이 접근 방법
이 문제는 해시맵(파이썬의 딕셔너리)을 활용하면 간단하게 해결할 수 있습니다. 풀이 단계는 다음과 같습니다.
- 상자별 공 개수를 저장할 빈 딕셔너리를 생성합니다.
- l부터 r까지의 각 숫자 i에 대해 다음을 수행합니다.
- 합계(total)를 0으로 초기화합니다.
- i의 각 자릿수 j를 모두 더해 total을 계산합니다.
- total이 딕셔너리에 없으면 해당 키를 0으로 초기화합니다.
- 해당 키의 값을 1 증가시킵니다.
- 딕셔너리의 모든 값 중 최댓값을 반환합니다. 이것이 곧 가장 많은 공이 담긴 상자의 공 개수입니다.
파이썬 구현 예제
아래 예제 코드를 통해 더 쉽게 이해할 수 있습니다. 참고로 원본 코드에서 변수명 dict는 파이썬 내장 타입을 가리키므로, 가독성과 안전성을 위해 box_count로 변경했습니다.
def solve(l, r):
box_count = {}
for i in range(l, r + 1):
total = 0
for j in str(i):
total += int(j)
if total not in box_count:
box_count[total] = 0
box_count[total] += 1
return max(box_count.values())
l = 15
r = 25
print(solve(l, r))실행 결과
입력:
15, 25
출력:
2
코드 설명 및 복잡도
str(i)로 숫자를 문자열로 변환한 뒤 한 글자씩 int()로 바꾸어 더하면 자릿수 합을 손쉽게 구할 수 있습니다. 모든 범위의 숫자를 한 번씩 순회하므로 시간 복잡도는 O((r − l + 1) × d)입니다. 여기서 d는 숫자의 자릿수입니다. 딕셔너리에는 서로 다른 자릿수 합의 개수만큼만 저장되므로 공간 복잡도 역시 매우 작습니다.
추가로, 문자열 변환 없이 divmod(i, 10)를 반복해 각 자릿수를 추출하는 방식으로도 동일한 결과를 얻을 수 있으며, 이 방법은 수치 연산만 사용하므로 성능 면에서 약간 더 유리합니다.