[프로그래머스] 위클리 10주차 - 교점에 별 만들기(JS)

문제 이해하기

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

  2x - y + 4 = 0
  -2x - y + 4 = 0
  -y + 1 = 0
  5x - 8y - 12 = 0
  5x + 8y + 12 = 0

• 좌표 평면 위에 그리면, 교점이 생기는데 정수로 표현되는 교점에 별을 그리면 아래 그림과 같다. 
  

  

• 위 그림을 문자열로 나타낼 때. 별이 그려진 부분은 `*`, 빈공간은 `.`으로 표현하면 다음과 같다. 
  

  

데이터 추상화

• 주어진 데이터 선분들의 교점을 구한다음 교점은  * 로 빈공간은  .  으로 그려야 한다. 
• 교점을 그리기 위해서 좌표 평면을 추상화해야 한다. 좌표 평면에는 x축, y축 모두 음수의 값이 있지만, 우리가 사용할 2차원 배열에는 음수로 접근이 불가능하다. 그렇기에 주어진 교점을 평행 이동하여 양수로 변경해줘야 함을 알 수 있다. 
• 우리가 사용할 배열은 좌표 평면의 어느부분에 위치할까? 1 사분면에 위치하는데 1 사분면을 세로로 뒤집은 모양임을 알 수 있다. 그렇다면 주어진 교점을 1 사분면이 세로로 뒤집은 모양으로 평행 이동시켜줘야 한다. 
• 교점(x, y)의 x의 값은 좌표에서 교점 중 x의 가장 작은 값을 만큼 우측(+)으로 평행이동하자.  
• 교점(x, y)의 y의 값은 좌표에서 교점 중 y의 가장 큰 값을 만큼 아래(-)로 평행이동하자. 

알고리즘 

1. 주어진 배열 데이터를 이용해 직선이 만나는 교점을 구하자. 두 직선이 만나는 교점을 구하는 구하는 식은 연립방정식을 이용해 구할 수 있다. 하지만 문제의 참고 사항에 두 교점을 구하는 식을 제공하고 있다. 
   

   

   참고사항

   위 식을 이용해서 우리는 교점을 구하는 함수를 만들어보자. 이때 교점은 정수만 취급하기 때문에 정수가 아닌 경우는 예외처리 해주자. 
   

   // 두선의 교점을 찾아내는 함수
   const getCrossPoint = ( [A, B, E], [C, D, F]) => {
     if( A * D - B * C === 0){
       return false;
     }
     const x = ((B * F) - (E * D)) / ((A * D) - (B * C));
     const y = ((E * C) - (A * F)) / ((A * D) - (B * C));
   
     // 정수인 경우 
     return Number.isInteger(x) && Number.isInteger(y) ? [x,y] : false;
   }

   
   
   
2. 좌표 평면에 교점을 그려야한다. 교점 정보를 따로 저장하여, 좌표 평면의 최적의 크기를 구한다. 
   최적의 가로 길이는 교점의 가장 큰 x좌표 - 교점의 가장 작은 x좌표를 뺀 값이고, 
   최적의 세로 길이는 교점의 가장 큰 y좌표 - 교점의 가장 작은 y좌표를 뺀 값이다. 
   이때 좌표는 배열로 표현되어야 되기 때문에 1씩 더해줘야 한다. 
   최적의 크기를 구하기 위해서는 교점의 좌표를 모아둘 필요가 있다. 교점의 좌표에서 큰 값과 작은 값을 추출하자.
   

   const crossPoint = [];
   line.forEach( r1 => line.forEach( r2 => 
   	getCrossPoint(r1, r2) ? crossPoint.push(getCrossPoint(r1, r2)) : null ))
   
   let xMin = Math.min( ...crossPoint.map(ele => ele[0]));
   let xMax = Math.max( ...crossPoint.map(ele => ele[0]));
   let yMin = Math.min( ...crossPoint.map(ele => ele[1]));
   let yMax = Math.max( ...crossPoint.map(ele => ele[1]));
   
   answer = Array.from( Array(yMax - yMin + 1) , _ => Array(xMax - xMin + 1).fill('.') );

3. 좌표 평면까지 모두 구현이 되었다. 이제 교점을 좌표 평면에 그려주자. 배열로 추상화하면서 좌표 또한 평행이동을 하게 되었다. 
   x좌표는 오른쪽으로 교점의 가장 작은 x좌표만큼 
   y좌표는 아래쪽으로 교점의 가장 큰 y좌표를 기준으로 y좌표만큼 
   이동하여 그려주면 문제는 해결된다. 
   

   crossPoint.forEach( ([x,y]) => {
     answer[yMax - y][x - xMin] = '*';
   })
   return answer.map( ele => ele.join(''));​

구현

function solution(line) {
    var answer = [];
    // 두선의 교점을 찾아내는 함수
    const getCrossPoint = ( [A, B, E], [C, D, F]) => {
        if( A * D - B * C === 0){
            return false;
        }
        const x = ((B * F) - (E * D)) / ((A * D) - (B * C));
        const y = ((E * C) - (A * F)) / ((A * D) - (B * C));
        
        // 정수인 경우 
        return Number.isInteger(x) && Number.isInteger(y) ? [x,y] : false;
    }
    const crossPoint = [];
    line.forEach( r1 => line.forEach( r2 => 
             getCrossPoint(r1, r2) ? crossPoint.push(getCrossPoint(r1, r2)) : null ))
    
    let xMin = Math.min( ...crossPoint.map(ele => ele[0]));
    let xMax = Math.max( ...crossPoint.map(ele => ele[0]));
    let yMin = Math.min( ...crossPoint.map(ele => ele[1]));
    let yMax = Math.max( ...crossPoint.map(ele => ele[1]));

    answer = Array.from( Array(yMax - yMin + 1) , _ => Array(xMax - xMin + 1).fill('.') );
    
    crossPoint.forEach( ([x,y]) => {
        answer[yMax - y][x - xMin] = '*';
    })

    return answer.map( ele => ele.join(''));
}

정리 및 느낀 점 

• 이번에 풀어본 문제는 좌표 평면을 배열로 표현하는 방법에 대해 알아볼 수 있었다.
• 알고리즘 분류로는 단순 구현 문제 라고 생각되고, 좌표 구하는 공식도 제공되었기에 참고해서 풀면 된다. 
• 괄호를 하지 않아서, 원하는 좌표의 값이 나오지 않았는데. 괄호 치는 부분도 염두하고 진행하자.

참고

https://programmers.co.kr/learn/courses/30/lessons/87377?language=javascript