숫자 n이 주어졌을 때, 이 숫자의 모든 부분 숫자(sub-number)들이 서로 다른 자릿수 곱(digit product)을 가지는지 확인해야 합니다. 여기서 n자리 숫자는 총 n*(n+1)/2개의 부분 숫자를 가질 수 있습니다. 예를 들어, 135의 부분 숫자는 1, 3, 5, 13, 35, 135이며, 어떤 수의 자릿수 곱은 그 수를 구성하는 각 자릿수들의 곱을 의미합니다.
예를 들어 입력이 n = 235라면, 부분 숫자는 [2, 3, 5, 23, 35, 235]이고, 각각의 자릿수 곱은 [2, 3, 5, 6, 15, 30]이 됩니다. 이 값들은 모두 서로 다르므로 출력 결과는 True입니다.
문제 해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
1. dig_prod() 함수 정의
- product 변수를 1로 초기화합니다.
- digits 리스트의 각 자릿수 d에 대해 product에 d를 곱합니다.
- 최종 product 값을 반환합니다.
2. solve() 메인 함수 구현
- num_str := 숫자 num을 문자열로 변환
- length := num_str의 길이
- digits := 길이가 length인 리스트로 초기화 (모든 값은 None)
- prod_set := 새로운 빈 집합 생성
- i를 0부터 length까지 반복하며 digits[i]에 num_str[i]를 정수로 변환하여 저장
- i를 0부터 length-1까지, j를 i부터 length-1까지 이중 반복하며 다음을 수행
- item := dig_prod(digits[i부터 j까지])로 부분 숫자의 자릿수 곱 계산
- 만약 item이 이미 prod_set에 존재한다면 False 반환 (중복 발견)
- 그렇지 않으면 prod_set에 item 추가
- 모든 반복이 끝나면 중복이 없으므로 True 반환
구현 예제 코드
def dig_prod(digits):
product = 1
for d in digits:
product *= d
return product
def solve(num):
num_str = str(num)
length = len(num_str)
digits = [None] * length
prod_set = set()
for i in range(0, length):
digits[i] = int(num_str[i])
for i in range(0, length):
for j in range(i, length):
item = dig_prod(digits[i:j+1])
if item in prod_set:
return False
else:
prod_set.add(item)
return True
n = 235
print(solve(n))입력
235
출력
True
동작 원리 설명
위 코드에서 dig_prod() 함수는 전달받은 자릿수 리스트의 곱을 계산하는 보조 함수입니다. solve() 함수는 먼저 입력 숫자를 문자열로 변환한 뒤 각 자릿수를 정수 리스트로 만듭니다. 그다음 이중 반복문을 통해 가능한 모든 연속된 부분 숫자 조합을 생성하고, 각 부분 숫자의 자릿수 곱을 집합(prod_set)에 저장합니다.
집합(set)은 중복을 허용하지 않는 자료구조이므로, 새로 계산된 자릿수 곱이 이미 집합에 존재하는지만 확인하면 됩니다. 하나라도 중복이 발견되면 즉시 False를 반환하고, 모든 부분 숫자의 자릿수 곱이 고유하다면 마지막에 True를 반환합니다.
예제에서 235의 경우 자릿수 곱이 [2, 3, 5, 6, 15, 30]으로 모두 고유하므로 True가 출력됩니다. 반면 223과 같은 숫자는 부분 숫자 2와 2의 자릿수 곱이 같아 False가 반환됩니다.