프로그래머스 Lv.2(JS)

Algorithm

프로그래머스 Lv.2(JS) - 당구 연습

Mar 21, 2023

Algorithm

Javascript

프로그래머스 Lv.2 당구 연습

문제 설명

프로그래머스의 마스코트인 머쓱이는 최근 취미로 당구를 치기 시작했습니다.

머쓱이는 손 대신 날개를 사용해야 해서 당구를 잘 못 칩니다. 하지만 끈기가 강한 머쓱이는 열심히 노력해서 당구를 잘 치려고 당구 학원에 다니고 있습니다.

오늘도 당구 학원에 나온 머쓱이에게 당구 선생님이”원쿠션”(당구에서 공을 쳐서 벽에 맞히는 걸 쿠션이라고 부르고, 벽에 한 번 맞힌 후 공에 맞히면 원쿠션이라고 부릅니다) 연습을 하라면서 당구공의 위치가 담긴 리스트를 건네줬습니다. 리스트에는 머쓱이가 맞춰야 하는 공들의 위치가 담겨있습니다. 머쓱이는 리스트에 담긴 각 위치에 순서대로 공을 놓아가며 “원쿠션” 연습을 하면 됩니다. 이때, 머쓱이는 항상 같은 위치에 공을 놓고 쳐서 리스트에 담긴 위치에 놓인 공을 맞춥니다.

머쓱이와 달리 최근 취미로 알고리즘 문제를 풀기 시작한 당신은, 머쓱이가 친 공이 각각의 목표로한 공에 맞을 때까지 최소 얼마의 거리를 굴러가야 하는지가 궁금해졌습니다.

당구대의 가로 길이 m, 세로 길이 n과 머쓱이가 쳐야 하는 공이 놓인 위치 좌표를 나타내는 두 정수 startX, startY, 그리고 매 회마다 목표로 해야하는 공들의 위치 좌표를 나타내는 정수 쌍들이 들어있는 2차원 정수배열 balls가 주어집니다. “원쿠션” 연습을 위해 머쓱이가 공을 적어도 벽에 한 번은 맞춘 후 목표 공에 맞힌다고 할 때, 각 회마다 머쓱이가 친 공이 굴러간 거리의 최솟값의 제곱을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

단, 머쓱이가 친 공이 벽에 부딪힐 때 진행 방향은 항상 입사각과 반사각이 동일하며, 만약 꼭짓점에 부딪힐 경우 진입 방향의 반대방향으로 공이 진행됩니다. 공의 크기는 무시하며, 두 공의 좌표가 정확히 일치하는 경우에만 두 공이 서로 맞았다고 판단합니다. 공이 목표 공에 맞기 전에 멈추는 경우는 없으며, 목표 공에 맞으면 바로 멈춘다고 가정합니다.

위 그림은 친 공이 벽에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

위 그림은 친 공이 꼭짓점에 맞았을 때의 움직임을 나타낸 그림입니다. 치기 전 공의 위치가 점 A입니다.

제한사항

3 ≤ m, n ≤ 1,000

0 < startX < m

0 < startY < n

2 ≤ balls의 길이 ≤ 1,000

balls의 원소는 [a, b] 형태입니다.

a, b는 머쓱이가 맞춰야 할 공이 놓인 좌표를 의미합니다.

0 < a < m, 0 < b < n

(a, b) = ( startX, startY )인 입력은 들어오지 않습니다.

입출력 예

m n startX startY balls result

10 10 3 7 [[7, 7], [2, 7], [7, 3]] [52, 37, 116]

m	n	startX	startY	balls	result
10	10	3	7	[[7, 7], [2, 7], [7, 3]]	[52, 37, 116]

풀이 코드

function solution(m, n, startX, startY, balls) {
  const symmPoints = [
    [-startX, startY],
    [startX + (m - startX) * 2, startY],
    [startX, -startY],
    [startX, startY + (n - startY) * 2],
  ];
  let result = [];

  const getDistance = (point1, point2) => {
    return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2;
  };

  for (const ball of balls) {
    let minDistance;

    if (ball[0] === startX) {
      const symmIdx = startX < m / 2 ? 0 : 1;
      const vertDistance =
        startY < ball[1]
          ? (startY + ball[1]) ** 2
          : (n * 2 - startY - ball[1]) ** 2;
      result.push(
        Math.min(getDistance(symmPoints[symmIdx], ball), vertDistance),
      );
      continue;
    }

    if (ball[1] === startY) {
      const symmIdx = startY < n / 2 ? 2 : 3;
      const horizDistance =
        startX < ball[0]
          ? (startX + ball[0]) ** 2
          : (m * 2 - startX - ball[0]) ** 2;
      result.push(
        Math.min(getDistance(symmPoints[symmIdx], ball), horizDistance),
      );
      continue;
    }

    symmPoints.map((symmPoint) => {
      let distance = getDistance(symmPoint, ball);
      minDistance = minDistance < distance ? minDistance : distance;
    });
    result.push(minDistance);
  }

  return result;
}

풀이 설명

𖣠 key point

시작점과 balls의 최단거리는 시작점의 대칭 좌표와 balls의 거리와 같다.

function solution(m, n, startX, startY, balls) {
  const symmPoints = [
    [-startX, startY],
    [startX + (m - startX) * 2, startY],
    [startX, -startY],
    [startX, startY + (n - startY) * 2],
  ];
  let result = [];
}

symmPoints에 시작점에 대한 대칭점을 배열로 저장한다.

function solution(m, n, startX, startY, balls) {
  //...
  const getDistance = (point1, point2) => {
    return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2;
  };
}

getDistance()는 두 점 사이의 거리의 제곱을 구하는 함수이다.

두 점 사이의 거리 공식

function solution(m, n, startX, startY, balls) {
  //...
  for (const ball of balls) {
    if (ball[0] === startX) {...}
    if (ball[1] === startY) {...}
    symmPoints.map((symmPoint) => {...});
  }
}

balls를 순회하며 시작 좌표와 balls 좌표의 x좌표 또는 y좌표가 동일한 경우와 그렇지 않은 경우로 나누어 생각한다.

x좌표가 같은 경우

function solution(m, n, startX, startY, balls) {
  //...
  for (const ball of balls) {
    if (ball[0] === startX) {
      const symmIdx = startX < m / 2 ? 0 : 1;
      const vertDistance =
        startY < ball[1]
          ? (startY + ball[1]) ** 2
          : (n * 2 - startY - ball[1]) ** 2;
      result.push(
        Math.min(getDistance(symmPoints[symmIdx], ball), vertDistance),
      );
      continue;
    }
    //...
  }
  return result;
}

시작점의 x좌표가 당구대 가로 길이의 절반보다 작은 경우, 대칭점 배열의 첫 번째 좌표([-startX, startY])를 사용하고 그렇지 않은 경우 두 번째 좌표([startX + (m - startX) * 2, startY])를 사용한다.

vertDistance는 처음 공이 수직으로 벽에 맞고 ball을 맞출 때의 거리이다.
getDistance 값과 vertDistance를 비교하여 더 작은 거리를 결괏값에 추가한다.

y좌표가 같은 경우

function solution(m, n, startX, startY, balls) {
  //...
  for (const ball of balls) {
    //...
    if (ball[1] === startY) {
      const symmIdx = startY < n / 2 ? 2 : 3;
      const horizDistance =
        startX < ball[0]
          ? (startX + ball[0]) ** 2
          : (m * 2 - startX - ball[0]) ** 2;
      result.push(
        Math.min(getDistance(symmPoints[symmIdx], ball), horizDistance),
      );
      continue;
    }
    //...
  }

  return result;
}

시작점의 y좌표가 당구대 세로 길이의 절반보다 작은 경우, 대칭점 배열의 세 번째 좌표([startX, -startY])를 사용하고 그렇지 않은 경우 네 번째 좌표([startX, startY + (n - startY) * 2])를 사용한다.
horizDistance는 처음 공이 수평으로 벽에 맞고 ball을 맞출 때의 거리이다.
getDistance 값과 horizDistance를 비교하여 더 작은 거리를 결괏값에 추가한다.

function solution(m, n, startX, startY, balls) {
  //...
  for (const ball of balls) {
    let minDistance;
    //...
    symmPoints.map((symmPoint) => {
      let distance = getDistance(symmPoint, ball);
      minDistance = minDistance < distance ? minDistance : distance;
    });
    result.push(minDistance);
  }

  return result;
}

balls의 x좌표 또는 y좌표가 처음 공의 좌표와 같지 않을 경우 symmPoints를 순회하며 대칭점과 balls 간의 최단거리를 찾아 결괏값에 추가한다.

References

프로그래머스 연습

https://school.programmers.co.kr/learn/challenges

Table Of Contents