970. Powerful Integers

문제)

세 정수 x, y, bound가 주어집니다.

bound 이하의 값 중에서 강력한 정수를 모두 찾아 리스트로 반환하세요.

강력한 정수란, 어떤 정수 i와 j에 대해 x^i + y^j 형태로 나타낼 수 있는 정수를 말합니다.

여기서 i >= 0 그리고 j >= 0입니다.

정답은 어떤 순서로든 반환할 수 있으며, 리스트에는 중복된 값이 포함되지 않아야 합니다.

 

문제 난이도 : 중

 

소요시간 및 풀이)

간단하게 제곱해준값을 비교해가면서 풀었다.

이 과정에서 예외처리를 제대로 해주지 않아서 시간초과가 발생했다.

중복을 허용하지 않기 위해 set사용하였다.

 

소요 시간 : 28분

 

정답 코드

class Solution 
{
public:
    vector<int> powerfulIntegers(int x, int y, int bound) 
    {
        set<int> result;  

        for (int i = 0; pow(x, i) <= bound; i++)
        {
            for (int j = 0; pow(y, j) <= bound; j++)
            {
                int value = pow(x, i) + pow(y, j);

                if (value <= bound)
                    result.insert(value);
                else
                    break; //더 큰 값이 나오면 break

                if (y == 1) 
                    break;  //y가 1일 때, 무한 루프 방지
            }
            if (x == 1)
                break;  //x가 1일 때, 무한 루프 방지
        }

        return vector<int>(result.begin(), result.end());
    }
};