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

해당 게시물은 leego 님의 티스토리 블로그를 참고하여 작성되었음을 미리 밝힙니다.

※ 2단계 문제이며 가장 어려움

해당 문제는 지문을 읽으면서도 멘탈이 너무 나가서 자세한 설명을 생략하고 꼭 필요한 부분만 주석을 달고 체크하겠음

출처 ) leego님의 티스토리 블로그

문제 시작

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 함수를 완성해주세요.

코딩 시작

function solution(line) {
    // 정수의 교점을 모두 찾는다
    function findInterSectionPoints() {
        const meetPoints = []
        
        for(let i = 0 ; i < line.length ; i ++) {
            for(let j = i+1 ; j < line.length ; j ++) {
                // 현재 좌표 및 다음 좌표의 x점, y점, 기울기를 구한다.
                const [curX,curY,curInc] = line[i]
                const [nextX,nextY,nextInc] = line[j] 
                
                // 기울기가 같다면 평행하기 때문에 교점이 생기지 않는다. 0 = 평행
                const Inclination = curX*nextY - curY*nextX
                
                if(Inclination) {
                    const meetX = (curY*nextInc - curInc*nextY) / Inclination
                    const meetY = (curInc*nextX - curX*nextInc) / Inclination
                    
                    if(Number.isInteger(meetX) && Number.isInteger(meetY)) {
                        meetPoints.push([meetX,meetY])
                    }
                }
            }
        }
        return meetPoints
    }
    
    // 찾은 교점을 별로 전환하며 최소의 보드 영역을 그림
    function drawBoardAndFindStar(meetPoints) {
        // 교점을 기준으로 최소영역의 교점을 넣는다.
        const [maxX, maxY, minX, minY] = meetPoints.reduce(
            ([maxX, maxY, minX, minY], [x, y]) => [
                Math.max(maxX,x),
                Math.max(maxY,y),
                Math.min(minX,x),
                Math.min(minY,y)
            ],
            [
                Number.MIN_SAFE_INTEGER,
                Number.MIN_SAFE_INTEGER,
                Number.MAX_SAFE_INTEGER,
                Number.MAX_SAFE_INTEGER,
            ]
        )
        
        // 최소화 할 수 있는 X, Y 좌표를 기준으로 보드를 그린다.
        let board = Array.from(Array(maxY-minY+1), () => Array(maxX-minX+1).fill('.'))

        // 그린 보드에 * 을 삽입한다
        meetPoints.forEach(([x,y]) => {
            board[maxY-y][x-minX] = '*'
        })
        
        return board.map(x => x.join(""))
    }
    
    return drawBoardAndFindStar(findInterSectionPoints())
}

이해하기 조차 많이 버거웠던 문제인만큼 오래 기억에 남을 것 같다.