점 찍기

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/140107

프로그래머스

 

 

문제 풀이

 

위와 같이, k 배수로 커지는 x와 y로 이뤄진 모든 좌표 중, 원 안에 있는 점의 숫자를 찾으면 되는 문제이다.

        for (int x = 0; x*k <= d; x++){
            for (int y = 0; y*k <= d; y++) {

                // 피타고라스 법칙에 의해서 [ x^2 + y^2 = d^2 ]
                if (Math.sqrt(Math.pow(x*k,2) + Math.pow(y*k,2)) <= d) {
                    answer++;
                }
                 else break;
            }
        }

 

 문제를 처음보면 위처럼 2중 for문(시간 복잡도 : O(n^2))으로 작성할 수 있는데, 그 k 최대값이 100만이고, d 최대값이100만이므로 시간 초과로 일부 테스트 케이스에서 실패하게 된다.

 

이를 해결해보자.

 

 일단 x² + y² = d²를 통해서 y = √(d² - x²)를 유추할 수 있다. 이를 통해 y축의 길이를 구한 뒤, k로 나누면 y축에서 유효한 점의 객수를 구할 수 있다. → y축에 대한 for문을 제거할 수 있다.

 

 

작성한 코드

class Solution {
    public long solution(int k, int d) {
        long answer = 0;

        for (int x = 0; x*k <= d; x++){

            double yMax = Math.sqrt( (long)Math.pow(d,2) - (long)Math.pow(x*k,2));

            answer += (long)(yMax / k) + 1; // 0인 경우 포함해야 하므로 +1
        }
        return answer;
    }
}