[프로그래머스] 교점에 별 만들기 (Lv 2) - javascript

문제

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
 

문제 더보기
 

🔑 크라메르 법칙

크라메르 법칙은 유일한 해를 가지며 변수와 방정식의 수가 같은 연립 일차 방정식의 해를 구하는 공식이다.

두 직선의 교점이 유일하게 존재한다면, 이 공식을 이용할 수 있다.

ax + by = e
cx + dy = f

 

• 교점
  

  

  
   

만약 아래와 같이 주어졌다면?

ax + by + e = 0
cx + dy +f = 0

 

• 교점 (위와 동일한 식임)
   
  

  

  
   
  AD - BC = 0 이면, 교점 없음 (기울기가 같다는 말 => 평행 or 일치)

 

📝 1차 풀이 (실패)

function solution(line) {

    let dots = [];

    line.forEach((v,idx) => {

        let [A, B, C] = v;

        for(let i = idx+1; i < line.length; i++) {
            let [a, b, c] = line[i];
            let dot = [(B*c-b*C)/(A*b-a*B), -(A/B)*(B*c-b*C)/(A*b-a*B)-C/B];

            if(A*b - a*B === 0) continue;
            if(dot[0] % 1 === 0 && dot[1] % 1 === 0) {
                if(checkOverlap(dot)) 
                    dots.push(dot);
            }
        }
    })

    // // dots 중복 제거
    function checkOverlap(arr) {
        for(let i = 0; i < dots.length; i++) {
            if(dots[i][0] === arr[0] && dots[i][1] === arr[1]) return false;
        }
        return true;
    }

    // 문자열로 출력하기
    // 최대 x, y 좌표 구하기 -> 사각형의 가로, 세로
    let x = dots.map(v => v[0]);
    let y = dots.map(v => v[1]);

    let minW = Math.min.apply(null, x);
    let maxW = Math.max.apply(null, x);
    let minH = Math.min.apply(null, y);
    let maxH = Math.max.apply(null, y);

    // 사각형 생성
    let answer = Array.from(new Array(maxH - minH + 1), () => new Array(maxW - minW + 1).fill('.'));

    dots.forEach(v => {
        answer[maxH-v[1]][v[0]-minW] = '*';
    })

    return answer.map(v => v.join(""));
}

 
구현은 제대로 했으나 교점을 찾는 공식이 잘못됐다.
다른 공식을 이용했는데, 너무 복잡하고 적절하지 않아 통과하지 못했다.
 

📝 2차 풀이 (통과)

function solution(line) {

    let dots = [];

    line.forEach((v,idx) => {

        let [A, B, E] = v;

        for(let i = idx+1; i < line.length; i++) {

            let [C, D, F] = line[i];

            if(A*D - B*C) {
            let dot = [(B*F-E*D)/(A*D-B*C), (E*C-A*F)/(A*D-B*C) ];
            if(dot[0] % 1 === 0 && dot[1] % 1 === 0) dots.push(dot);
            }
        }
    })

    let x = dots.map(v => v[0]);
    let y = dots.map(v => v[1]);

    let minW = Math.min.apply(null, x);
    let maxW = Math.max.apply(null, x);
    let minH = Math.min.apply(null, y);
    let maxH = Math.max.apply(null, y);

    let answer = Array.from(new Array(maxH - minH + 1), () => new Array(maxW - minW + 1).fill('.'));

    dots.forEach(v => {
        answer[maxH-v[1]][v[0]-minW] = '*';
    })

    return answer.map(v => v.join(""));
}

 

설명

function solution(line) {

    let dots = [];

    // 교점 리스트 구하기
    line.forEach((v,idx) => { 

        let [A, B, E] = v; // 첫번째 직선 방정식에 변수 할당

        for(let i = idx+1; i < line.length; i++) {

            let [C, D, F] = line[i]; // 두번째 직선 방정식에 변수 할당

            if(A*D - B*C) { // 두 직선의 기울기 같음 => 교점 없음
            let dot = [(B*F-E*D)/(A*D-B*C), (E*C-A*F)/(A*D-B*C) ]; 
            if(dot[0] % 1 === 0 && dot[1] % 1 === 0) dots.push(dot); // 정수 교점이면 추가
            }
        }
    })

    // 입력할 사각형 생성하기
    let x = dots.map(v => v[0]); // x좌표만 모은 배열
    let y = dots.map(v => v[1]); // y좌표만 모은 배열

    let minW = Math.min.apply(null, x); 
    let maxW = Math.max.apply(null, x);
    let minH = Math.min.apply(null, y);
    let maxH = Math.max.apply(null, y);

    let answer = Array.from(new Array(maxH - minH + 1), () => new Array(maxW - minW + 1).fill('.')); // 위에서 구한 식으로 사각형의 2차원 배열 만들기 *1

    dots.forEach([x,y] => {
        answer[maxH-y][x-minW] = '*'; // *2
    })

    return answer.map(v => v.join("")); // 배열을 문자열로 변환 -> 반환
}

 

dots에 교점을 추가하는 부분에서 중복 검사를 넣었는데, 그게 더 실행시간이 오래 걸려서 삭제했다.
문자열은 먼저 .로 가득한 사각형 모양 2차원 배열을 만들고, 교점들을 순회하면서 *로 변환했다.
 

1. 사각형 모양을 2차원 배열을 만드는 과정

   • 세로 길이 : maxH - minH + 1
   • 가로 길이 : maxW - minW + 1
      

2. 별을 채워넣을 때는 x값과 y값의 특성을 생각해서 구해야 한다.
   y를 위쪽이 +이므로 maxH-y
   x는 왼쪽이 -이므로 최소값을 뺀 x-minW
    

• 정확도 테스트 결과

  

 

---

참고

leego.tistory.com