[프로그래머스] 교점에 별 만들기 /JavaScript

 

 

 

교점에 별 만들기

 

https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 10주차_교점에 별 만들기

 

 

 

 

 

참고 사항

Ax + By + E = 0Cx + Dy + F = 0

두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

 

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

 

 

 

 

풀이

function solution(line) {
  const getIntersectionPoint = () => {
    let points = [];    // 정수로 이루어진 교점을 담을 배열

    for (let i = 0, len = line.length; i < len; i++) {
      for (let j = i + 1; j < len; j++) {
        const [a, b, e] = line[i];
        const [c, d, f] = line[j];

        // 직선의 기울기를 구해 비교한다. 기울기가 같다면 교점이 생기지 않는다.
        const slope = a * d - b * c;

        if (slope) {
          const pointX = (b * f - e * d) / slope;
          const pointY = (e * c - a * f) / slope;
          // x, y 좌표가 모두 정수인 교점만을 pints배열에 넣어준다.
          if (Number.isInteger(pointX) && Number.isInteger(pointY)) {
            points.push([pointX, pointY]);
          }
        }
      }
    }
    return points;
  };

  const drawingStar = (points) => {
    // 최소한의 보드를 그리기 위해 교점들의 최소, 최댓값을 구한다.
    const [maxX, maxY, minX, minY] = points.reduce(
      ([maxX, maxY, minX, minY], [x, y]) => [
        Math.max(maxX, x),
        Math.max(maxY, y),
        Math.min(minX, x),
        Math.min(minY, y),
      ],
      [
        Number.MIN_SAFE_INTEGER,
        Number.MIN_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
      ]
    );

    // 보드를 생성한다.
    let board = Array.from(Array(maxY - minY + 1), () =>
      Array(maxX - minX + 1).fill(".")
    );

    // 교점의 위치에 별을 그린다.
    points.forEach(([x, y]) => {
      board[maxY - y][x - minX] = "*";
    });

    return board.map((x) => x.join(""));
  };

  return drawingStar(getIntersectionPoint());
}

 

 

 

 

문제를 정리하면,

 

1️⃣ 직선의 모든 교점을 찾기 (단, 모든 좌표가 정수로 표현돼야한다)

2️⃣ 찾은 교점에 별 그리기 ( 격자판의 크기는 모든 별을 표시하면서, 최소한의 크기여야 한다.)

 

 

 

직선의 모든 교점 찾기

const getIntersectionPoint = () => {
    let points = [];    // 정수로 이루어진 교점을 담을 배열

    for (let i = 0, len = line.length; i < len; i++) {
      for (let j = i + 1; j < len; j++) {
        const [a, b, e] = line[i];
        const [c, d, f] = line[j];

        // 직선의 기울기를 구해 비교한다. 기울기가 같다면 교점이 생기지 않는다.
        const slope = a * d - b * c;

        if (slope) {
          const pointX = (b * f - e * d) / slope;
          const pointY = (e * c - a * f) / slope;
          // x, y 좌표가 모두 정수인 교점만을 pints배열에 넣어준다.
          if (Number.isInteger(pointX) && Number.isInteger(pointY)) {
            points.push([pointX, pointY]);
          }
        }
      }
    }
    return points;
  };

교점을 찾는 역할은getIntersectionPoint 에서 담당한다.

 

문제에서 교점을 구하는 공식을 친절하게 알려주었다.

 

먼저 모든 직선 사이의 교점을 찾아야 하기 때문에 이중 for문을 돌려주었다. 두 직선의 기울기 a * d 와 b * c 가 같다면 교점이 생기지 않기 때문에, 기울기가 같지 않을 때만 교점을 찾는다.

 

const pointX = (b * f - e * d) / slope;
const pointY = (e * c - a * f) / slope;

문제에서 알려준 공식으로 교점의 x, y 좌표를 구한다.

 

if (Number.isInteger(pointX) && Number.isInteger(pointY)) {
            points.push([pointX, pointY]);
}

좌표 모두가 정수일 때 points 배열에 넣어준다.

 

 

 

 

 

찾은 교점에 별 그리기

const drawingStar = (points) => {
    // 최소한의 보드를 그리기 위해 교점들의 최소, 최댓값을 구한다.
    const [maxX, maxY, minX, minY] = points.reduce(
      ([maxX, maxY, minX, minY], [x, y]) => [
        Math.max(maxX, x),
        Math.max(maxY, y),
        Math.min(minX, x),
        Math.min(minY, y),
      ],
      [
        Number.MIN_SAFE_INTEGER,
        Number.MIN_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
      ]
    );

    // 보드를 생성한다.
    let board = Array.from(Array(maxY - minY + 1), () =>
      Array(maxX - minX + 1).fill(".")
    );

    // 교점의 위치에 별을 그린다.
    points.forEach(([x, y]) => {
      board[maxY - y][x - minX] = "*";
    });

    return board.map((x) => x.join(""));
  };

교점들의 최소, 최댓값을 구한다.

 

 

const [maxX, maxY, minX, minY] = points.reduce(
      ([maxX, maxY, minX, minY], [x, y]) => [
        Math.max(maxX, x),
        Math.max(maxY, y),
        Math.min(minX, x),
        Math.min(minY, y),
      ],
      [
        Number.MIN_SAFE_INTEGER,
        Number.MIN_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
        Number.MAX_SAFE_INTEGER,
      ]
    );

Number.MAX_SAFE_INTEGER 는 JavaScript에서 안전한 최대 정수값(2^53 - 1).

Number.MIN_SAFE_INTEGER 는 JavaScript에서 안전한 최소 정수값(-(2^53 - 1))을 나타낸다.

 

// 보드를 생성한다.
    let board = Array.from(Array(maxY - minY + 1), () =>
      Array(maxX - minX + 1).fill(".")
    );

이제 구한 최소, 최댓값을 이용하여 보드를 생성한다. 값의 변환을 위해 "."를 채운 2차배열로 생성해주었다.

 

// 교점의 위치에 별을 그린다.
    points.forEach(([x, y]) => {
      board[maxY - y][x - minX] = "*";
    });

이제 교점 배열을 돌면서 해당 위치에 별을 그려준다.

새로운 보드판을 생성하였기 때문에 교점의 x, y값을 그대로 옮기면 안된다.

 

두가지를 고려해주어야 하는데, 첫번째는 보드의 ( 0, 0)이 바뀌었다는 것. 두번째는 좌표에서는 y축이 위로 갈 수록 커지므로 보드에 그릴때는 거꾸로 그려주어야 한다는 점이다.

 

교점을 보드에 옮기기 위해서는 각각의 좌표에서 최솟값을 빼주면 된다. board[y - minY][x - minX]가 된다.

 

이제 y축은 거꾸로 그려주어야 하기 때문에 보드의 길이에서 위에서 구한 y축 값을 빼준다.

보드의 y축 길이는 maxY - minY 이므로 maxY - minY - (y - minY) 정리하면 maxY - y가 된다.

 

 

 

return board.map((x) => x.join(""));

배열이었던 y축 값을 문자열로 바꿔준 후 결과를 return해준다.