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

 

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

프로그래머스

 

 

---

1. 문제 설명

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

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은.으로 표현하면 다음과 같습니다.

"..........."  
".....*....."  
"..........."  
"..........."  
".*.......*."  
"..........."  
"..........."  
"..........."  
"..........."  
".*.......*."  
"..........."  

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

따라서 정답은

"....*...."  
"........."  
"........."  
"*.......*"  
"........."  
"........."  
"........."  
"........."  
"*.......*"  

입니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• line의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
  • line의 가로(열) 길이는 3입니다.
  • line의 각 원소는 [A, B, C] 형태입니다.
  • A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
  • 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
  • A = 0이면서 B = 0인 경우는 주어지지 않습니다.
• 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

 

 

---

2. 입출력

 

 

---

3. 문제풀이

function solution(line) {
    var answer = [];
    var points = []; // 교점의 좌표를 담는 배열
    var maxX = Number.MIN_SAFE_INTEGER; // X좌표 최댓값
    var minX = Number.MAX_SAFE_INTEGER; // X좌표 최솟값
    var maxY = Number.MIN_SAFE_INTEGER; // Y좌표 최댓값
    var minY = Number.MAX_SAFE_INTEGER; // Y좌표 최솟값
    
    // 1) 모든 선들의 교점을 찾기 위한 2중 for문 반복
    for (var i=0; i<line.length; i++) {
        var [A, B, E] = line[i];
        for (var j=i+1; j<line.length; j++) {
            var [C, D, F] = line[j];
            var x = (B*F - E*D) / (A*D - B*C); // 교점 X좌표 구하는 공식
            var y = (E*C - A*F) / (A*D - B*C); // 교점 Y좌표 구하는 공식
            
            // 2) 교점이 존재하면서, X좌표와 Y좌표가 정수일 경우만 체크
            if(A*D - B*C != 0 && Number.isInteger(x) && Number.isInteger(y)) {
                points.push([x, y]);  
                
                // 3) 2차원 배열로 만들기 위한 범위를 구하기 위해 X,Y좌표의 최대,최소 값을 구한다.
                maxX = Math.max(maxX, x);
                minX = Math.min(minX, x);
                maxY = Math.max(maxY, y);
                minY = Math.min(minY, y);
            }
        }    
    }
    
    // 4) 교점의 좌표를 표시하기 위한 2차원 배열을 만든다.
    answer = Array.from(Array(maxY - minY + 1), () =>
      Array(maxX - minX + 1).fill(".")
    );
    
    // 5) 교점의 좌표를 표시한다.
    points.forEach(([x, y]) => {
      answer[maxY - y][x - minX] = "*";
    });
    
    return answer.map((x) => x.join(""));;
}