[Leetcode 633번 문제] 633. Sum of Square Numbers

문제 상황

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

c가 두개의 제곱수의 합으로 나타낼 수 있는지 확인하라는 문제

입력

정수 c

출력

제곱수의 합으로 나타낼 수 있는지에 대한 불값

과정

일단 c는 제곱수의 합이기 때문에 특정

c - 특정 제곱수가 제곱수인지 확인하는 문제여도됨.

그럼 모든 제곱수들을 저장해놓고 그냥 해시하면 되지 않을까?

대충 2 ** 16번의 계산만 하면 돼서 문제 없다고 생각했다.

알고리즘 개요도

 

알고리즘

class Solution {
    typedef long long ll;
    unordered_map<int, int> container;
public:
    bool judgeSquareSum(int c) {
        ll limit = (ll) (1 << 31) - 1;
        ll start = 0;
        while (start * start <= c)
        {
            container[(int) start * start] = 1;
            start++;   
        }
        for (unordered_map<int, int>::iterator ac = container.begin() ; ac != container.end(); ac++)
        {
            if (container.find(c - ac -> first) != container.end())
            {
                return true;
            }
        }
        return false;
    }
};

문제는 어렵지 않게 풀었지만 막상 실행 결과가 하위 5% 수준이어서 다른 사람의 코드를 확인해봤다.

 

리트코드 상위 1퍼 풀이

class Solution {
public:
    bool judgeSquareSum(int c) 
    {
        long long int i=1,j=sqrt(c);
        if(j*j==c)
        return true;
        while(i<=j)
        {
           long long sum = (i*i)+(j*j);
           if(sum==c)
           // 투포인터로 접근. 
           return true;
           // 작을경우 왼쪽을 올리고
           else if(sum<c)
           i++;
           // 높을경우 오른쪽을 낮추면 O(n) 시간인데 메모리 저장이라는
           // 오버헤드 없이 문제 풀 수 있어서 더 빠름
           else
           j--;
        }
        return false;
        
    }
};

일단 투포인터로 문제를 풀었다. 사실 투포인터나 내 방식이나 O(sqrt(c))의 시간안에 문제를 풀 수 있지만 

1. 시작과 끝점을 알고 있으므로 데이터를 저장할 필요 없이 현재의 내 지점에서 1을 더하고 빼면 된다.
2. 양쪽을 시작점 끝점으로 나눴기 때문에 둘의 계산값이 c의 제곱보다 작을경우 왼쪽을 올리고 반대의 경우 오른쪽을 내리는 방식으로 직렬화 할 수 있다.

이런 두가지 이유 때문에 투포인터를 이용하면 데이터를 저장하는 오버헤드 없이 더 빠르게 풀 수 있다.