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

문제 출처

프로그래머스 lev2 - 교점에 별 만들기

나의 풀이

다른 풀이

for i 마다 for j = i+1로 순회해야 중복없이 모든 직선 간의 교점을 탐색할 수 있다.

아래와 같은 경우를 제외한 좌표 경우의 수를 구한다. (좌표는 주어진 공식에 따라 구하면 된다)
(1) 두 직선 간의 평행이거나 일치인 경우 if (mod === 0) continue;
(2) 정수가 아닌 경우 if (xNum % mod || yNum % mod) continue;

문자열로 교환하기 위해서는 길이를 알아야 한다.
가로/세로 별로 최대값최소값을 구하면 전체 길이를 구할 수 있다.

좌표에는 음수가 포함되는데 배열에 배치하려면 양수로 변환해줘야 하므로
[maxH - y][x - minW]를 통해 양수로 변환해준다.

2중 배열이 아니라 배열 내 문자열 구조이므로 join()으로 변환해서 return해준다.

function solution(line) {
  const result = [];
  let [maxH, minH, maxW, minW] = [-Infinity, Infinity, -Infinity, Infinity];

  line.forEach(([a, b, e], i) => {
    for (let j = i + 1; j < line.length; j++) {
      const [c, d, f] = line[j];
      const mod = a * d - b * c;
      if (mod === 0) continue;

      const xNum = b * f - e * d;
      const yNum = e * c - a * f;
      if (xNum % mod || yNum % mod) continue;

      const [x, y] = [xNum / mod, yNum / mod];
      result.push([x, y]);
      maxW = Math.max(x, maxW);
      minW = Math.min(x, minW);
      maxH = Math.max(y, maxH);
      minH = Math.min(y, minH);
    }
  });

  const table = new Array(maxH - minH + 1)
    .fill(null)
    .map(() => new Array(maxW - minW + 1).fill(null).map(() => "."));

  result.forEach(([x, y]) => (table[maxH - y][x - minW] = "*"));
  return table.map((v) => v.join(""));
}

// console.log(
//   solution([
//     [2, -1, 4],
//     [-2, -1, 4],
//     [0, -1, 1],
//     [5, -8, -12],
//     [5, 8, 12],
//   ])
// );
// console.log(solution([[0, 1, -1], [1, 0, -1], [1, 0, 1]]))
// console.log(solution([[1, -1, 0], [2, -1, 0]]))

1. 점의 좌표 4개가 주어졌을 때의 두 직선의 교점

px = (x1y2 - y1x2)(x3 - x4) - (x1 - x2)(x3y4 - y3x4) / (x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4) 
py = (x1y2 - y1x2)(y3 - y4) - (y1 - y2)(x3y4 - y3x4) / (x1 - x2)(y3 - y4) - (y1 - y2)(x3 - x4)

(x1-x2)(y3-y4) - (y1-y2)(x3-x4) = 0일 때 평행이거나 일치 (교점x)

2. 방정식이 다음과 같을 떄

// 표준형 
y = m1*x + b1
y = m2*x + b2 

px = (b2-b1)/(m1-m2)
py = m1 * (b2-b1)/(m1-m2) + b1

// 일반형 
a1*x + b1*y + c1 = 0
a2*y + b2*y + c2 = 0

px = (b1c2 - b2c1)/(a1b2-a2b1)
py = -a/b * px - c1/b1

표준형의 경우 m1=m2이면 평행이거나 일치
일반형의 경우 a1b2 - a2b1 = 0이면 평행이거나 일치

참고

[수학] 두 직선의 교점 구하기