https://programmers.co.kr/learn/courses/30/lessons/87377
Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
예를 들어, 다음과 같은 직선 5개를
좌표 평면 위에 그리면 아래 그림과 같습니다.
이때, 모든 교점의 좌표는 (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 | 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]] | ["*"] |
입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
직선 y = 1, x = 1, x = -1는 다음과 같습니다.
(-1, 1), (1, 1) 에서 교점이 발생합니다.
따라서 정답은
"*.*"
입니다.
입출력 예 #3
직선 y = x, y = 2x는 다음과 같습니다.
(0, 0) 에서 교점이 발생합니다.
따라서 정답은
"*"
입니다.
입출력 예 #4
직선 y = x, y = 2x, y = 4x는 다음과 같습니다.
(0, 0) 에서 교점이 발생합니다.
따라서 정답은
"*"
입니다.
Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.
또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.
function solution(line) {
var points = [];
var stars = [];
for(let i =0; i<line.length; i++){
for(let j = i+1 ;j<line.length; j++){ // 교점 찾기
var a = line[i][0];
var b = line[i][1];
var e = line[i][2];
var c = line[j][0];
var d = line[j][1];
var f = line[j][2];
var point = [(b*f-e*d)/(a*d-b*c), (e*c-a*f)/(a*d-b*c)]
points.push(point);
}
}
points = points.filter(a=>Number.isInteger(a[0])&&Number.isInteger(a[1])); // x,y가 정수가 아닌 교점 제거
points.sort((a,b)=>{
return b[0]-a[0];
});
var maxX =points[0][0];
var minX =points[points.length-1][0];
points.sort((a,b)=>{
return b[1]-a[1]
});
var maxY = points[0][1];
var minY =points[points.length-1][1];
for(let i =0; i<=maxY-minY; i++){ // . 생성
var s = [];
for(let j =0; j<=maxX-minX; j++){
s.push(".");
}
stars.push(s)
}
points.forEach(a=>{ // 교점 별로 바꾸기
stars[maxY-a[1]][a[0]-minX] = '*'
})
return stars.map(a=>a.join(''));
}