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

https://school.programmers.co.kr/learn/courses/30/lessons/140107?language=javascript 

프로그래머스

 

문제

 

풀이

문제를 조금 풀어서 설명 하자만 x,y 축에 k의 배수 씩 점을 찍을 건데 원점과 거리가 d를 넘으면 점을 찍지 않는 것!

문제 풀이의 핵심은  원점과의 거리를 구하는 것입니다.

d^2 = x^2 + y^2

위 공식을 기반으로 점을 찍을 좌표가 원점과의 거리가 d 보다 크지 않으면 answer를 올려주면 됩니다.

 

주의 해야할 점은 d,k의 인풋이 최대 1000000 이기 때문에 이중 반복문돌리면 시간 초과 나게 됩니다. 

예를 들어

function solution(k, d) {
    var answer = 0;
        
    for(let x =0 ; x <= d; x+= k) {
        for(let y = 0; y<=d; y+=k){
            
            if((x**2 + y**2) <= d*d){
                answer++;
            }
        }
    }
    
    return answer;

}

이렇게 이중 반복으로 코드를 짜면 워스트 케이스가 O(n^2) 이니까 백만일 때 시간초과 납니다.

반복문 한 번에 O(n)에 해결하는 방법을 찾아야 하는데 ,
x 좌표 값을 반복 할 때 최대 y 값 좌표를 찾아서 해당 k로 나누면 해당 x 좌표에 해당하는 점들을 계산할 수 있습니다.

Code

function solution(k, d) {
    let answer = 0;
    for(let i = 0; i <= d; i+=k){
        let y = Math.sqrt(d**2 - i**2); // 최대 y 값
        answer += Math.floor(y/k) + 1; // 해당 y 값의 k 배수 갯수 + 1
    }
    return answer;
}