[Leetcode] 970. Powerful Integers

April Leetcode Challenge 2021에서 4월 30일에 (PST) 출시된 문제를 풀어보도록 하겠다.

 

문제는 아래 링크를 참고하길 바란다.

leetcode.com/problems/powerful-integers/

Powerful Integers - LeetCode

이 문제를 처음 봤을때는 뭔가 다른 트릭이 필요한가? 라는 생각이 들었는데 그냥 brute-force 로 푸는 방법보다 딱히 더 빠른 알고리즘이 떠오르지 않아서 그냥 풀고 솔루션을 봤다. 뭐, 순열도 생각하고 그랬지만 아니나 다를까 그냥 푸는 게 답이었다.......물론 주의해야 할 포인트가 1개 있었다.

 

문제를 읽어보면 3개의 정수 x, y, bound 가 주어지고, bound 보다 작거나 같은 x, y의 powerful 정수들 합을 리스트에 넣어서 리턴하라는 것이다. 어떤 순서로 리턴하든 상관이 없고 대신에 각 변수는 최대 1번 사용되어야 한다고 한다.

 

필자의 풀이는 아래와 같다.

class Solution {
    public List<Integer> powerfulIntegers(int x, int y, int bound) {
        List<Integer> result = new ArrayList<>(); // 결과 출력을 위한 리스트
        List<Integer> list1 = powerfulInteger(x, bound); // x의 거듭제곱들
        List<Integer> list2 = powerfulInteger(y, bound); // y의 거듭제곱들
        for (int i = 0; i < list1.size(); i++) { // list1 에서 1개
            for (int j = 0; j < list2.size(); j++) { // list2 에서 1개
                int twoSum = list1.get(i) + list2.get(j); // 더해주고
                if (twoSum <= bound // bound 보다 작거나 같으면서
                && !result.contains(twoSum)) { // 결과 리스트에 포함되지 않는 것
                    result.add(twoSum); // 결과 리스트에 추가
                }
            }
        }
        return result; // 결과 리스트 리턴
    }
    
    private List<Integer> powerfulInteger(int n, int bound) {
        List<Integer> list = new ArrayList<>();
        if (n == 1) { // 1인 경우에는 아무리 곱해도 1
            list.add(1); // 그래서 1만 추가하고 
            return list; // 결과 리턴
        }
        int power = 1; // 당연히 0으로는 안됨
        while (power < bound) { // bound 보다 작아야 함, 같으면 안됨
            list.add(power); // 우선 1부터 넣고
            power *= n; // 거듭제곱수를 넣어줌
        }
        
        return list; // 거듭제곱 리스트 리턴
    }
}

x, y 의 거듭제곱들 중 bound 보다 작은 것들을 모아서 각각 리스트에 담은 다음에, for-loop 을 통해 두 개의 합을 구해주면 된다. 주의해야 할 부분은 거듭제곱을 구할 때에 1인 경우를 처리해주지 않으면 무한반복에 빠질 수 있으니 그것을 주의해야 한다. 그리고 당연하겠지만 두 개의 거듭제곱을 구해야하니, 1개의 거듭제곱을 구할때는 bound 미만 조건으로 구해야 나머지 1개가 1인 경우에 이하가 될 수 있다.

 

이 문제의 시간복잡도는 x의 거듭제곱을 구하기 위해서 A 라는 비용을 쓰고, y의 거듭제곱을 구하기 위해서 B 라는 비용을 썼다고 한다면, $$ O (A * B), A = log_{x} bound, B = log_{y} bound $$ 가 된다.

그리고 공간복잡도도 위와 같은 비용을 가진다.