[이진탐색] 점 찍기

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

첫번째 풀이(시간초과)

처음엔 단순하게 가능한 경우를 모두 구한 뒤, 두 점사이의 거리가 d보다 작은 점만 가려냈다

 

function solution(k, d) {
    var answer = 0;
    const group = [];
    const count = Math.floor(d/k);
    for (let i = 0; i <= count; i++) {
        const x = i * k;
        for (let j = 0; j <= count; j++) {
            const y = j *k;
            group.push([x, y]);
        }
    }
    
    for (const [x, y] of group) {
        if (Math.sqrt(x*x + y*y) <= d) {
            answer++;
        }
    }
    return answer;
}

 

두번째 풀이(성공)

1,000,000 => O( NlogN ) => 내부순회량을 줄이기에 포커스를 맞추고 고민했다

 

간단히 생각해보니 쉬웠다
x를 순회하면서 최대y값을 구하고, 각 x마다 찍을수 있는 y점의 갯수를 더한다

function solution(k, d) {
    var answer = 0;
    // k배씩 증가
    for (let x = 0; x <= d; x+=k) {
        const maxY = Math.sqrt(d*d - x*x);
        answer += Math.floor(maxY/k)+1;
    }
    return answer;
}