프로그래머스 JS 점 찍기 (반지름 d의 원에 k마다 존재하는 좌표 수)

점 찍기 (*) 문제 보기

문제 조건

 

// 1. x축으로 a*k, y축으로 b*k 마다 점 찍기

// 2. 원점과 거리가 d를 넘으면 점 찍지 않음

 

---

문제 풀이 첫번째 (실패)

function solution(k, d) {
//   const coordinate = Array(d + 1)
//     .fill()
//     .map(() => Array(d + 1).fill(0));

  let count = 0;

  for (let i = 0; i <= d; i += k) {
    for (let j = 0; j <= d; j += k) {
      if (i + j <= d || Math.sqrt(i ** 2 + j ** 2) <= d) {
        // coordinate[i][j] = 1;
        count++;
      } else {
        continue;
      }
    }
  }

  //   console.log(coordinate, count);
  return count;
}

1,000,000 * 1,000,000 이기 때문에 이중 for문으로 구현한 결과는 시간 초과이다.

 

좌표에 실제로 점을 찍는다면 나쁘지 않은 선택이었겠지만,

역시나 수학적으로 접근해야겠구나 싶었다.

---

문제 풀이 두번째 (성공)

function solution(k, d) {
  let count = 0;

  for (let i = 0; i <= d; i += k) {
    count += Math.floor(Math.sqrt(d ** 2 - i ** 2) / k) + 1;
  }

  return count;
}

for문을 한 번만 순회하면서도 구할 수 있다.

 

문제에서 주어진 예시를 참고해보면 다음과 같다.

 

(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), 

(1, 0), (1, 1), (1, 2), (1, 3), (1, 4), 

(2, 0), (2, 1), (2, 2), (2, 3), (2, 4), 

(3, 0), (3, 1), (3, 2), (3, 3), (3, 4), 

(4, 0), (4, 1), (4, 2), (4, 3), 

(5, 0) 

 

 

a^2 + b^2 <= d^2 를 만족하는 수들을 찾으면 된다.

 

d=5일 때,

a^2 + b^2 <= 25

 

a가 0일 때, b는 [0,1,2,3,4,5]

a가 1일 때, b는 [0,1,2,3,4]

...

a가 4일 때, b는 [0,1,2,3]

a가 5일 때, b는 [0]

 

조건과 일치하는 것을 확인할 수 있다.

k마다 점을 찍어야 한다는 조건이 있기 때문에

만족하는 수의 길이를 k로 나눈 값의 정수부를 가져야 한다.

 

k=2일 때,

[0,1,2,3,4,5]는 0,2,4 에 찍히게 된다.

k=3일 때,

[0,1,2,3,4,5] 0,3에 찍히게 된다.

 

y=0에 위치한 수들로 인해 항상 최소 1개의 만족하는 수를 갖도록 한다.

    count += Math.floor(Math.sqrt(d ** 2 - i ** 2) / k) + 1;