두 개의 값, 즉 숫자 num과 정수 k가 주어졌을 때, num의 자릿수 중 연속된 k개의 자릿수를 곱해 얻을 수 있는 가장 큰 값을 찾아야 합니다. 이때 num은 항상 k개 이상의 자릿수를 가진다고 가정합니다.
예를 들어 입력이 num = 52689762, k = 4라면 출력은 3024가 됩니다. 연속된 4개의 자릿수 중 곱이 가장 큰 조합은 (8 × 9 × 7 × 6) = 3024이기 때문입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 최댓값을 저장할 변수
largest를 0으로 초기화합니다. num을 10^(k-1)으로 나눈 몫이 0보다 큰 동안 반복합니다. 즉, 아직 검사하지 않은 자릿수가 k개 이상 남아 있는 동안 계속 진행합니다.- 현재
num의 마지막 k개 자릿수를digits에 저장합니다 (num mod 10^k). digits의 각 자릿수를 하나씩 곱해 후보값cand를 계산합니다. 도중에 0이 등장하면 곱셈 결과가 무조건 0이 되므로 즉시 반복을 중단합니다.largest와cand중 더 큰 값으로largest를 갱신합니다.num을 10으로 나누어 마지막 자릿수를 제거하고, 다음 연속 구간을 검사합니다.- 모든 구간을 검사한 뒤
largest를 반환합니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
파이썬 코드
class Solution:
def solve(self, num, k):
largest = 0
while num // 10 ** (k - 1) > 0:
digits = num % 10 ** k
cand = 1
while digits > 0:
cand *= digits % 10
if cand == 0:
break
digits //= 10
largest = max(largest, cand)
num //= 10
return largest
ob = Solution()
num = 52689762
k = 4
print(ob.solve(num, k))
입력
52689762, 4
출력
3024
더 간결한 대안: 문자열과 math.prod 활용
숫자를 문자열로 변환한 뒤 슬라이딩 윈도우 방식으로 처리하면 훨씬 직관적으로 표현할 수 있습니다. 파이썬 3.8 이상에서는 math.prod를 사용해 한 줄로 곱을 계산할 수 있습니다.
from math import prod
def solve(num, k):
s = str(num)
return max(prod(map(int, s[i:i + k])) for i in range(len(s) - k + 1))
print(solve(52689762, 4)) # 3024
복잡도 분석
시간 복잡도: O(n × k). 여기서 n은 num의 자릿수 개수입니다. 각 시작 위치마다 k개의 자릿수를 곱하기 때문입니다.
공간 복잡도: O(1). 추가 저장 공간이 거의 필요하지 않습니다.
정리하면, 이 문제는 모든 연속 구간을 하나씩 검사하는 완전 탐색 방식으로 충분히 해결할 수 있으며, 0이 등장하는 순간 조기 종료하면 불필요한 연산을 줄일 수 있습니다.