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

# 문제 원문

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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예
line / result

[[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]]	["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"]
[[0, 1, -1], [1, 0, -1], [1, 0, 1]]	["*.*"]
[[1, -1, 0], [2, -1, 0]]	["*"]
[[1, -1, 0], [2, -1, 0], [4, -1, 0]]	["*"]

# 문제 풀이

사실상 수학문제다. xy그래프 위의 여러 직선들의 교점을 구하는 문제로 직선 방정식이나 좌표 관련한 수학적 지식의 유무에 따라서 난이도가 달라진다. 개인적으로는 어려웠다. 그외 자잘한 core dump 라거나 오버플로우 문제등 때문에 수학적 능력이 부족하다면 더욱 헤매게 되는 문제인 것 같다. (문제점을 찾기가 어려웠다.) 수학 관련한 기초적인 지식들이 머릿속에 전혀 존재하지 않는다는 슬픈 사실을 체감하게 해준 문제이다. 수학공부를 다시 해야할꺼 같다. 직선의 교차점을 구하고 비교하는 부분에 대해서 선명하게 그려지지 않는다. 추후 다시 풀어봐야겠다.

# 솔루션 플로우

1. 맵 크기를 MAS_SAFE_INTEGER로 초기화해준다.
2. 입력 받은 line을 순회하면서 모든 라인의 교차점이 존재하는지 확인한다.
3. 교차점이 존재한다면 맵크기를 비교하여서 조정해준후 교차점의 좌표 star를 구한다.
4. 구해진 맵크기에 맞춰서 '.' 요소로 이루어진 2차원 배열 starMap을 얻는다.
5. 교차점 배열 star를 순회하면서 각 좌표에 '*'별을 삽입한다.
6. starMap배열을 순회하면서 2차원배열을 1차원 배열로 join해준다.
7. 얻어진 result를 반환한다.

1. FP

function solution(line) {
    const Max = Number.MAX_SAFE_INTEGER;
    const mapSize = [Max, -Max, Max, -Max];
    const star = line.reduce((result, left, idx) => {
        line.slice(idx + 1, line.length)
            .forEach((right) => {
                const [a, b, c] = left;
                const [x, y, z] = right;
                const div = a * y - b * x;
                if (div !== 0) {
                    const lineX = b * z - c * y;
                    const lineY = c * x - z * a;
                    if (lineX % div === 0 && lineY % div === 0) {
                        const starX = lineX / div;
                        const starY = lineY / div;

                        mapSize[0] = Math.min(mapSize[0], starX);
                        mapSize[1] = Math.max(mapSize[1], starX);
                        mapSize[2] = Math.min(mapSize[2], starY);
                        mapSize[3] = Math.max(mapSize[3], starY);
                        result.push([starX, starY]);
                    }
                }
            });
        return result;
    }, []);

    const starMap = new Array(Math.abs(mapSize[3] - mapSize[2]) + 1).fill(true)
        .map((_) => new Array(Math.abs(mapSize[1] - mapSize[0]) + 1).fill('.'));
    star.forEach((current) => {
        const [x, y] = current;
        starMap[mapSize[3] - y][x - mapSize[0]] = '*';
    });

    return starMap.map((row) => row.join(''));
}