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

문제 출처

프로그래머스 lev2 - 점 찍기

나의 풀이

1차시도(81.3/100)

시간초과

const possible = (y, x, k, d) => {
  let cnt = 0
  while((Math.sqrt(Math.pow((y*k), 2) + Math.pow((x*k), 2)) <= d)) {
    console.log(y*k, x*k)
    x++
    cnt++
  }
  return cnt
}

const solution = (k, d) => {
  let answer = 0
  let y = 0

  while(y <= d/k) {
    answer += possible(y, 0, k, d)
    y++
  }

  return answer
}

2차시도 (실패)

일일이 ++하는 게 문제인가 싶어서,

y좌표를 확정했을 때 x 좌표의 최대값을 possible()의 인자로 넘겨줬다.
그리고 d보다 크면 바로 x을 반환하고
d보다 작으면 x를 하나씩 줄여가면서 x+1을 반환한다.

그렇게 해서 answer 값을 계산하면 여기에는 (0,0)이 포함되지 않으므로 최종적으로 반환할 때도 +1을 해서 반환해야 한다.

그래도 여전히 while문을 2중으로 순회하므로 의미가 없는 것 같다.

const possible = (y, x, k, d) => {
  console.log(y, x)
  if(Math.sqrt(Math.pow((y*k), 2) + Math.pow((x*k), 2)) <= d) return x
  while(Math.sqrt(Math.pow((y*k), 2) + Math.pow((x*k), 2)) > d) {
    x--
  } 
  return x+1
}

const solution = (k, d) => {
  let answer = 0

  for(let y=0; y<=d/k; y++) {
    answer += possible(y, d/k, k, d)
  }

  return answer+1
}

다른 풀이

원의 중심이 (a,b)일 때 반지름이 r인 원의 방정식은
(x-a)^2 + (y-b)^2 = r^2

내부에만 점이 찍히므로
점들은 원 내부에 존재해야 한다.

function solution(k, d) {
  let answer = 0;
  for (let x = 0; x <= d; x += k) {
    // x값을 통해 y의 최대값 도출
    const maxY = (d ** 2 - x ** 2) ** 0.5;
    // maxY가 k로 딱 나누어 떨어지면 1을 더해준다
    answer += Math.ceil(maxY / k) + (maxY % k === 0 ? 1 : 0);
  }
  return answer;
}

다른 풀이 2

프로그래머스 점 찍기 javascript

최대값을 찾아서, 그 최대값을 개수로 바로 answer에 추가하는 방법

function solution(k, d) {
  let answer = 0;
  const c = d ** 2;
  let left = d - (d % k); // k의 배수로 left 시작 값을 초기화
  let right = 0;
  while (right <= d) {
    // left 제곱과 right 제곱을 더한 값이 d의 제곱(c)보다 낮다면
    if (left ** 2 + right ** 2 <= c) {
      // right를 k 만큼 증가
      answer += Math.floor(left / k) + 1;
      right += k;
    } else {
      // left를 k 만큼 감소
      left -= k;
    }
  }
  return answer;
}

console.log(solution(2, 4))
console.log(solution(1, 5))

참고

프로그래머스 점 찍기 javascript