[프로그래머스] 점 찍기

문제

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍습니다.
원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.
예를 들어, k가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return 하는 solution 함수를 완성하세요.

풀이

완전탐색을 하게 되고 범위 안에 있는 좌표를 모두 탐색해야 한다.
그런게 그렇게 하면 당연히 시간 초과가 날게 뻔했다.
따라서 효율적인 방법을 찾아야 했다.
완전 탐색을 하지만 좀 더 효율적인 방식을 생각한 것이 바로 행렬이다.
만일 (2,1)이라는 좌표가 규칙에 맞는 좌표라고 하면 (1, 2)도 이에 해당한다는 것을 이용했다.
좌표를 순서대로 나열하게 되면
|(0, 0)|(1, 0)|(2, 0)|(3, 0)|
|(0, 1)|(1, 1)|(2, 1)|(3, 1)|
|(0, 2)|(1, 2)|(2, 2)|(3, 2)|
|(0, 3)|(1, 3)|(2, 3)|(3, 3)|

x, y좌표가 같은 대각선 아랫쪽만을 보자.
이 아랫부분에서 가능한 좌표들을 구하고 나면 자연스레 그 위쪽도 갯수가 같게 된다.

public long solution(int k, int d) {
        long answer = 0;
        Set<Integer> set = new HashSet<>();

        for(int i = 0; i * k <= d; i++) {
            int x = i * k;
            for(int j = i; j * k <= d; j++) {
                int y = j * k;
                double num = Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
                if (num <= d && x == y) {
                    if (!set.contains(x)) {
                        set.add(x);
                    }
                } else if (num <= d) {
                    answer++;
                }
            }
        }

        return answer * 2 + set.size();
    }

대각선 부분은 Set에 담아주어 마지막이 그 수를 더해주었다.
당연히 시간을 많이 줄였다고 생각했지만 시간초과가 3개... 따흑....

결국 다른 방법을 참고해였다.
결론은 원의방정식을 이용해야 하는 것이었다.
대체 여기서 원의방정식을 어떻게 생각하는건지...?

y <= sqrt(d^2 - x^2)이 성립하니까 for문 한번에 구하는 것이 가능하다...
y = sqrt(d^2 - x^2)를 하게 되면 x좌표당 0 ~ y범위까지는 모두 가능한 범위가 되기 때문에 이를 모두 더하면 된다.

import java.util.*;
import java.lang.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        for(long i = 0; i * k <= d; i++) {
            long x = i * k;
            long y = (long) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2)) / k;

            answer += y + 1;
        }

        return answer;
    }
}

https://github.com/Win-9/Algorism/tree/main/programers/%EC%A0%90%20%EC%B0%8D%EA%B8%B0