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 | 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인 경우 두 직선은 평행 또는 일치합니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
우선 문제에서 제공해준 교점 구하는 함수를 만든다. 좌표 두개를 넣었을때 가능한 교점 리턴 하는 함수 생성
1. 먼저 선에서 나올 수 있는 교점을 모두 구함 meetArr에 저장 -> 위에서 만든 함수 이용
2. meetArr에서 평행하지 않고 정수가 아닌 값은 거르기
3. 거른 meetArr에서 최대 X,Y, 최소 X,Y찾기
4. 가로 = (최대 X - 최소 X + 1) , 세로 = (최대 Y - 최소 Y + 1) 배열을 만들고 .으로 채우기
5. meetArr을 순회하면서 각 점에 해당하는 것을 *로 돌린다.
6. 이후에 값들을 합쳐서 문자열 배열로 만듬.
7. 그 값을 뒤집어서 리턴
function coorFun(coord1, coord2){
let [A,B,E] = coord1;
let [C,D,F] = coord2;
if((A*D) - (B*C) === 0){
return 0;
}
let x = ((B * F) - (E * D)) / ((A*D) - (B*C));
let y = ((E * C) - (A * F)) / ((A*D) - (B*C));
return [x,y];
}
function solution(line) {
var meetArr = [];
for(var i = 0;i<line.length;i++){
for(var j = i+1;j<line.length;j++){
meetArr.push(coorFun(line[i],line[j]));
}
}
//교점 거르기 => 평행하지 않고 정수인 것만 모으기
meetArr = meetArr.filter((element)=>{
//평행하지 않고
if(element!==0){
//정수로만 이루어진 것
if(element[0]===Math.floor(element[0]) && element[1]===Math.floor(element[1])){
return true;
}
else{
return false;
}
}
else{
return false;
}
})
//최대 y,x 최소 y,x값 찾기
var maxY = Number.MIN_SAFE_INTEGER;
var maxX = Number.MIN_SAFE_INTEGER;
var minY = Number.MAX_SAFE_INTEGER;
var minX = Number.MAX_SAFE_INTEGER;
meetArr.forEach((element)=>{
if(element[0]>maxX){
maxX = element[0];
}
if(element[0]<minX){
minX = element[0];
}
if(element[1]>maxY){
maxY = element[1];
}
if(element[1]<minY){
minY = element[1];
}
})
var answer = Array.from(Array(maxY-minY+1),()=>new Array(maxX- minX+1).fill("."))
meetArr.forEach((element)=>{
answer[element[1]-minY][element[0]-minX] = "*";
})
answer = answer.map(element=>element.join(""));
return answer.reverse();
}
이번 문제는 문제가 길고 구할게 많아서 최대한 기능을 쪼개서 각각을 구현했다. 그 덕분에 틀린 부분을 찾아내기 수훨했고, 다른 문제보다 빠르게 풀어냈던 것 같다.