알고리즘 문제 중 하나인 강력한 정수(Powerful Integers) 문제를 파이썬으로 해결하는 방법을 살펴보겠습니다.
문제 정의
두 개의 양의 정수 x와 y가 주어졌을 때, 어떤 정수가 x^i + y^j 형태로 표현될 수 있다면(i ≥ 0, j ≥ 0) 그 정수를 '강력한 정수'라고 부릅니다. 우리의 목표는 주어진 값 bound 이하인 모든 강력한 정수의 목록을 구하는 것입니다.
예시로 이해하기
예를 들어 x = 2, y = 3, bound = 10이라고 가정해 봅시다. 이 경우 출력 결과는 다음과 같습니다.
[2, 3, 4, 5, 7, 9, 10]
각 값이 강력한 정수에 해당하는 이유는 아래와 같습니다.
- 2 = 2⁰ + 3⁰
- 3 = 2¹ + 3⁰
- 4 = 2⁰ + 3¹
- 5 = 2¹ + 3¹
- 7 = 2² + 3¹
- 9 = 2³ + 3⁰
- 10 = 2⁰ + 3²
해결 접근 방식
이 문제는 지수 조합을 체계적으로 탐색하는 방식으로 해결할 수 있습니다. 핵심 로직은 다음과 같습니다.
- 지수 변수 a, b를 각각 0으로 초기화하고, 결과를 저장할 빈 리스트 res를 준비합니다.
- x = 1이고 y = 1인 경우: 두 수의 거듭제곱은 항상 1이므로 가능한 값은 2 하나뿐입니다. bound가 2 이상이면 [2]를 반환합니다.
- x = 1만 해당되는 경우: y의 거듭제곱에 1을 더한 값들만 bound 이하일 때까지 반복해서 추가합니다.
- y = 1만 해당되는 경우: x의 거듭제곱에 1을 더한 값들을 같은 방식으로 추가합니다.
- 그 외의 일반적인 경우: x^a + 1이 bound 이하인 동안 반복하면서, x^a + y^b가 bound 이하면 결과에 추가하고 b를 증가시킵니다. bound를 초과하면 a를 증가시키고 b를 0으로 초기화하여 다음 조합을 탐색합니다.
마지막으로 set()을 활용해 중복된 값을 제거한 후 결과를 반환하면 됩니다.
파이썬 구현 코드
위 알고리즘을 파이썬 코드로 구현하면 다음과 같습니다.
class Solution: def powerfulIntegers(self, x, y, bound): a, b = 0, 0 res = [] if x == 1 and y == 1: if bound >= 2: res.append(2) elif x == 1: while y ** b + 1 <= bound: res.append(y ** b + 1) b += 1 elif y == 1: while x ** a + 1 <= bound: res.append(x ** a + 1) a += 1 else: while x ** a + 1 <= bound: if x ** a + y ** b <= bound: res.append(x ** a + y ** b) b += 1 else: a += 1 b = 0 return list(set(res)) ob = Solution() print(ob.powerfulIntegers(2, 3, 10))
실행 결과 확인
입력
x = 2, y = 3, bound = 10
출력
[2, 3, 4, 5, 7, 9, 10]
마무리
이 문제의 핵심은 특수 케이스(x 또는 y가 1인 경우)를 별도로 처리하면서, 일반적인 경우에는 이중 반복문을 통해 모든 거듭제곱의 합을 효율적으로 탐색하는 것입니다. bound의 크기가 제한적이기 때문에 시간 복잡도 면에서도 충분히 실용적인 해법입니다. set()을 이용한 중복 제거까지 적용하면 깔끔하고 정확한 결과를 얻을 수 있습니다.