어떤 숫자 N이 주어졌을 때, N에서 최소한의 자릿수(0개일 수도 있음)를 삭제하여 만들 수 있는 가장 큰 완전세제곱수(perfect cube)를 구하는 문제입니다. 주어진 숫자에서 어떤 자릿수든 자유롭게 삭제할 수 있습니다.
여기서 완전세제곱수란 어떤 정수 M에 대해 N = M³이 성립하는 수를 의미합니다.
예를 들어 입력이 806이라면 출력은 8입니다. 숫자 806에서 '0'과 '6'을 삭제하면 '8'만 남는데, 이는 2³ = 8로 완전세제곱수이기 때문입니다.
문제 해결 접근 방식
이 문제는 다음 두 단계로 나누어 해결할 수 있습니다.
1단계: 사전 처리(preProcess)
- N보다 작거나 같은 모든 완전세제곱수를 미리 생성합니다.
- 1부터 N의 세제곱근까지 반복하면서 각 i³ 값을 문자열 형태로 리스트에 저장합니다.
2단계: 탐색(solve)
- 생성된 세제곱수 리스트를 내림차순(큰 수부터)으로 정렬합니다.
- 각 세제곱수가 주어진 숫자의 부분 수열(subsequence)인지 확인합니다. 즉, 숫자의 자릿수를 순서대로 훑으면서 해당 세제곱수의 모든 자릿수가 순서대로 등장하는지 검사합니다.
- 가장 큰 세제곱수부터 검사하므로, 처음으로 부분 수열 조건을 만족하는 값이 곧 정답이 됩니다.
- 아무것도 찾지 못하면 "Not Possible"을 반환합니다.
부분 수열 여부를 확인하는 방식 덕분에, 남은 자릿수 개수가 곧 삭제해야 할 최소 자릿수 개수와 일치하게 됩니다.
구현 예제
다음 파이썬 코드로 전체 로직을 구현할 수 있습니다.
import math
def preProcess(n):
temp_cubes = list()
for i in range(1, math.ceil(n ** (1. / 3.))):
cube = i ** 3
cubeString = str(cube)
temp_cubes.append(cubeString)
return temp_cubes
def solve(num, temp_cubes):
temp_cubes = temp_cubes[::-1] # 큰 수부터 탐색
totalCubes = len(temp_cubes)
for i in range(totalCubes):
temp = temp_cubes[i]
digitsInCube = len(temp)
index = 0
digitsInNumber = len(num)
for j in range(digitsInNumber):
if num[j] == temp[index]:
index += 1
if digitsInCube == index:
return temp
return "Not Possible"
def getLargestCube(n):
temp_cubes = preProcess(n)
num = str(n)
ans = solve(num, temp_cubes)
return ans
n = 806
print(getLargestCube(n))입력
806
출력
8
동작 원리 설명
입력이 806인 경우를 살펴보겠습니다.
- preProcess 함수는 806의 세제곱근(약 9.3)까지의 정수들에 대해 1, 8, 27, 64, ..., 729를 문자열로 저장합니다.
- solve 함수는 이 리스트를 뒤집어 729부터 차례대로 검사합니다.
- "729"는 806의 부분 수열이 아니므로 건너뛰고, 다음 후보들을 검사합니다.
- "8"은 806에서 첫 번째 자릿수 '8'과 일치하므로 부분 수열 조건을 만족하고, 결과로 8이 반환됩니다.
이 알고리즘의 시간 복잡도는 세제곱수 후보 개수(O(N^(1/3)))와 각 후보에 대한 부분 수열 검사 비용(O(자릿수 길이))의 곱으로 표현되며, 일반적인 입력 크기에서 매우 효율적으로 동작합니다.