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

문제링크
https://programmers.co.kr/learn/courses/30/lessons/87377

문제 설명

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

입출력 예

문제풀이

1. line 배열을 돌면서 생길 수 있는 정수 교점을 intersect배열에 푸시한다.
2. x 최소,최대값 y최소, 최대값을 변수로 설정하여 x,y최소값이 음수이면 최소절댓값을 더해주고 양수이면 빼준다.
3. x,y값을 바꿔준다.
4. y최소, 최대값만큼 배열을 생성하여 x최소, 최대값만큼 .을 반복하면 배열을 생성한다.
5. intersect배열의 첫번째 값이 answer index값과 동일하다면 intersect 두번째 값 위치에 *을 넣어준다.
6. 정답을 역으로 정렬하여 반환한다.

코드

function solution(line) {
    var intersect = [];
    for(let i=0; i<line.length-1; i++){
        for(let j=i+1; j<line.length; j++){
            const[a,b,e] = line[i];
            const[c,d,f] = line[j];
            if((b*f-e*d)/(a*d-b*c)%1==0 && (e*c-a*f)/(a*d-b*c)%1==0)
                intersect.push([(b*f-e*d)/(a*d-b*c), (e*c-a*f)/(a*d-b*c)]);
        }
    }
    let yMax = Math.max(...intersect.map(v => v[1]));
    let yMin = Math.min(...intersect.map(v => v[1]));
    let xMax = Math.max(...intersect.map(v => v[0]));
    let xMin = Math.min(...intersect.map(v => v[0]));
    intersect.map(v => {
        if(yMin < 0) v[1] += Math.abs(yMin);
        else v[1] -= Math.abs(yMin);
        if(xMin < 0) v[0] += Math.abs(xMin);
        else v[0] -= Math.abs(xMin);
        
        let tmp = v[1];
        v[1] = v[0];
        v[0] = tmp;
    })
    let answer = new Array(yMax-yMin+1).fill(".".repeat(xMax-xMin+1));
    answer = answer.map((v,i) => {
        intersect.map(e => {
            if(i == e[0]) v = v.substring(0,e[1]) + "*" + v.substring(e[1]+1);
        })
        return v;
    })
    return answer.reverse();
}

다른사람 코드

function solution(line) {
    const m = [...line.map(([a, b, e]) => line.map(([c, d, f]) => [b * f - e * d, e * c - a * f, a * d - b * c]))
                      .flat().filter(([x, y, z]) => z && !(x % z || y % z))
                      .map(([x, y, z]) => [x / z, y / z])
                      .reduce((m, v) => m.set(v.join(","), v), new Map()).values()];
    const [[xa, xb], [ya, yb]] = [m.map(v => v[0]), m.map(v => v[1])].map(v => [Math.min(...v), Math.max(...v)]);
    const s = Array(yb - ya + 1).fill(false).map(() => Array(xb - xa + 1).fill(false));
    for (const [x, y] of m) s[yb - y][x - xa] = true;
    return s.map(l => l.map(v => v ? "*" : ".").join(""))
};

리팩토링

function solution(line) {
    var intersect = [];
    for(let i=0; i<line.length-1; i++){
        for(let j=i+1; j<line.length; j++){
            const[a,b,e] = line[i];
            const[c,d,f] = line[j];
            if((b*f-e*d)/(a*d-b*c)%1==0 && (e*c-a*f)/(a*d-b*c)%1==0)
                intersect.push([(e*c-a*f)/(a*d-b*c), (b*f-e*d)/(a*d-b*c)]);
        }
    }
    
    let xMin = Math.min(...intersect.map(v => v[1]));
    let yMin = Math.min(...intersect.map(v => v[0]));
    intersect.map(v => {
        yMin < 0 ? v[0] += Math.abs(yMin) : v[0] -= Math.abs(yMin);
        xMin < 0 ? v[1] += Math.abs(xMin) : v[1] -= Math.abs(xMin);
    })
    
    let xMax = Math.max(...intersect.map(v => v[1]));
    let yMax = Math.max(...intersect.map(v => v[0]));
    let answer = new Array(yMax+1).fill(".".repeat(xMax+1));
    
    return answer.map((v,i) => {
        intersect.map(e => i == e[0]? v = v.substring(0,e[1]) + "*" + v.substring(e[1]+1) : v = v);
        return v;
    }).reverse();
}

TIL

• 좌표와 배열의 순서는 역순이다.