[프로그래머스] Level2 - 점 찍기(Javascript)

프로그래머스

▶ 문제 요약

1. 좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍는다. 

2. 원점(0,0)으로부터 x축 방향으로 a*k,  y축 방향으로 b*k만큼 떨어진 위치에 점을 찍는다. 

3. 원점과 거리가 d를 넘는 위치에는 점을 찍지 않는다. 

 

▶ 실패 코드

function pow(number) {
    return Math.pow(number, 2);
}

function solution(k, d) {
    let answer = 0;
    
    
    for (let x = 0; x <= d; x += k) {
        for (let y = 0; y <= d; y += k) {
            if (pow(d) - pow(x) >= pow(y)) {
                answer ++;
            }
        }
    }
    return answer;
}

▶ 실패 원인

아무 생각없이 2중 for문을 돌렸더니 시간 초과가 떠서 보니 제한사항에 k랑 d의 범위가 1,000,000까지다. 그러니 이걸 이중 반복문을 돌리면 당연히 시간 초과가 난다. 문제를 너무 대충 읽은 내 탓이다. 

 

▶ 성공 코드

function pow(number) {
	return Math.pow(number, 2);
}

function solution(k, d) {
    let answer = 0;
    
    
    for (let x = 0; x <= d; x+=k) {
    	// 원의 방정식 활용 
        maxY = Math.sqrt(pow(d) - pow(x));
        
        // 만약에 k로 나눠 떨어지면 + 1을 해야한다. 
        answer += Math.ceil(maxY / k) + (MaxY % k === 0 ? 1 : 0)
    
    }
    
    return answer;
    
}

▶ 풀이 과정

1. 이중 반복문을 사용했더니 위에 처럼 시간 초과가 떴으니 다른 방법을 활용해야 한다. 이 문제는 점들이 원의 내부에 찍힌다는 것이 포인트고, 원의 방정식 x^2 + y^2 = d^2이다. 내부에 점이 찍히는 것이라서 d^2이하이면 된다. sqrt 제곱근 함수를 사용한 이유는 y^2의 값을 구하는 것이 아니라 y를 구하려면 제곱을 오른쪽으로 이항하고 제곱근이 된다. 

 

2. 만약에 k로 나눠 떨어지면 +1을 하는 경우는 예로 설명하겠다. maxY가 4이고, k = 2이다 그럼 몫이 2가 된다. (0, 0), (0, 2), (0, 4)가 되어야 하는데 1개가 부족하다 그래서 1을 더해준다. 다른 예시로 maxY가 4.2이고, k = 2가 된다면, 몫은 2.1이 되고 Math.ceil() 올림 함수 때문에 3이되고 (0,0), (0, 2), (0,4)까지의 위치의 개수를 잘 얻을 수 있다.