[leetcode #633] Sum of Square Numbers

Problem

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

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: c = 3
Output: false

Example 3:

Input: c = 4
Output: true

Example 4:

Input: c = 2
Output: true

Example 5:

Input: c = 1
Output: true

Constraints:

0 <= c <= 2³¹ - 1

Idea

주어진 수 c가 임의의 두 수를 각각 제곱한 값의 합이 되는지 확인하는 문제다. 번뜩이는 아이디어가 없어서 직관적으로 문제를 풀려고 했다. 우선 주어진 수 c의 제곱근을 먼저 구한 뒤 그 수보다 작은 모든 정수의 제곱을 set에 더한다. 이후 set의 각 정수를 탐색하면서 c - (set 내에 있는 정수) 값이 set에 포함되어 있는지 다시 탐색한다. 있으면 true를 리턴하고 루프를 다 돌았다면 false를 리턴한다.

알고리즘

1. HashSet을 만든다.
2. c의 제곱근보다 작은 정수(>= 0)에 한해 루프를 돌면서 제곱이 되는 수를 set에 더한다.
3. set에 있는 정수를 탐색하면서 (c-i)값이 set에 포함되어 있는지 확인한다.
   a. 포함되어 있으면 true를 리턴한다.
   b. 포함되어 있지 않다면 다시 탐색한다.
4. set에 있는 수를 전부 탐색했는데도 true를 리턴하지 못 했다면 false를 리턴한다.

Solution

class Solution {
    public boolean judgeSquareSum(int c) {
        Set<Integer> set = new HashSet<Integer>();

        for (int i=0; i <= (int) Math.sqrt(c); i++) {
            set.add(i*i);
        }

        for (int i : set) {
            if (set.contains(c-i))
                return true;
        }

        return false;
    }
}

아무 생각없이 풀어서 그런지 결과는 최악이다. Solution을 보니 binary search로 푸는 법이 있던데 set을 이용하는 방법보단 훨씬 현명한 방법인 것 같다. 언제쯤 binary search가 익숙해지려나...

Reference

https://leetcode.com/problems/sum-of-square-numbers/