[프로그래머스] 점 찍기 (Java)

프로그래머스

접근 방식

 1사분면의 4분원 안에서 k값에 따라 찍을 수 있는 점의 개수를 모두 구하는 문제이다(원과 관련된 식을 전혀 몰라도 해결 가능). 직관적인 방식은 최초 접근처럼 이중 for문을 사용하여 각 x, y 좌표가 0, 0 으로부터 d 이하의 거리에 위치해있는지를 체크하는 것인데 이럴 경우 시간초과가 나게된다.  탐색을 한 번만 하여 문제를 해결하려면 각 x좌표에 대해 최대 y좌표값을 구하면 된다. 최대 y를 maxY라고 지칭한다면 피타고라스의 정리에 의해 x^2 +  maxY^2 = d^2 이므로 maxY 값은 Math.sqrt(d*d - x*x)가 된다. 이렇게 구한 maxY값을 k로 나눈 후 1을 더하면 각 x값에 대한 최대 y값을 구하게 된다. 1을 더해주는 이유는 x, 0 좌표를 포함시켜야하기 때문이다.

로직 설명

- (반복) 최대 거리값 d를 넘지 않을 때까지 0부터 시작하여 k씩 더해주며 x를 증가시켜나간다:

1) maxY값을 구한다.

2) answer에 maxY / k + 1을 더해준다. 

Note

- 인풋의 크기때문에 제곱과 더하기를 수행할 때 int범위를 넘어설 수 있어 long타입으로 변수를 선언해야 한다.

최초 접근방식 (이중 for문으로 시간초과)

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        
        int[][] arr = new int[d + 1][d + 1];
        
        for(int i = 0; i <= d; i += k){
            for(int j = 0; j <= d; j += k){
                if(Math.sqrt(i * i + j * j) <= d && arr[i][j] == 0){
                    arr[i][j] = 1;
                    answer++;
                }
            }
        }
        
        return answer;
    }
}

정답코드 (한 번만 탐색)

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

        for(long x = 0; x <= d; x += k){
            long maxY = (long) Math.sqrt(d*d - x*x); 
            answer += maxY / k + 1;
        }
        
        return answer;
    }
}