[ 프로그래머스 ] 140107 점 찍기

Link | 프로그래머스 140107번 문제 : 점 찍기

📌 About

Brute force으로 각각의 점의 좌표를 구하는 방법도 있다.

하지만 k = 1, d = 1,000,000이면 최대 $1,000,000^2$ 의 연산을 해야 한다.

때문에 최대 1,000,000의 연산으로 끝낼 수 있어야 한다.

📌 Solution

X 좌표만을 보면 0, k, 2k, 3k, 4k... (x ≦ d) 가 되는 것을 알 수 있다.

각각의 X 좌표에 대해 $x^2 + y^2 ≦ d^2$ 인 최대 y값을 구하면 된다.

이를 code으로 표현하면 다음과 같다.

(int) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2))

이 때 Y값 또한 k씩 늘어나므로 Y / k + 1 을 하면 X에 대한 점의 개수를 구할 수 있다.

(int) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2)) / k + 1

위의 식을 바탕으로 X 값 마다의 Y 개수를 구하여 전체합을 반환해주면 된다.

📌 Code

GitHub Repository

FOR

public long solution(int k, int d) {
	long sum = 0L;
    for (long x = 0L; x <= d; x += k)
    	sum += (int) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2)) / k + 1;
    return sum;
}

STREAM

class Solution {
    public long solution(int k, int d) {
        return LongStream.iterate(0, x -> x <= d, x -> x + k)
                .map(x -> (int) Math.sqrt(Math.pow(d, 2) - Math.pow(x, 2)) / k + 1).sum();
    }
}