[2024] day 170. Leetcode 633. Sum of Square Numbers

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 6월 17일 (월)
Leetcode daily problem

633. Sum of Square Numbers

https://leetcode.com/problems/sum-of-square-numbers/?envType=daily-question&envId=2024-06-17

Problem

음수가 아닌 정수 c가 주어지면 a2 + b2 = c가 되는 두 개의 정수 a와 b가 있는지 확인한다.

Solution

two pointers

주어진 양의 정수 c가 두 정수 a,b의 제곱의 합으로 표현될 수 있는지 확인하기 위해서 a^2 + b^2 =c 인 두 정수가 존재하는 지 확인하기 위해서 투 포인터를 사용할 수 있다.
a,b의 두 개의 포인터를 사용해서 a는 0, b는 √c에서 시작한다.
a^2+b^2를 계산해서 a^2+b^2=c 이면 true를 반환하고, a^2+b^2 <c이면 a를 1 증가, a^2+b^2>c 이면 b를 감소 시킨다.
a가 b보다 커지면 해당 반복을 멈추고 false를 반환한다.

Code

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        a,b = 0, int(math.sqrt(c))
        
        while a<=b:
            if a**2 + b**2 == c:
                return True
            elif a**2 + b**2 > c:
                b -=1
            
            else:
                a+=1
                
        return False

Complexicity

시간 복잡도

while 루프에서 a가 b보다 커질대 까지 반복하는데, 최악의 경우 a,b가 √c까지 이동하는 것이므로 최대 반복은 √c로 시간 복잡도는 O(√c) 이다.

공간 복잡도

상수의 변수만을 할당하므로 공간복잡도는 O(1)이다.