🎯문제
Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.
예를 들어, 다음과 같은 직선 5개를
2x - y + 4 = 0-2x - y + 4 = 0-y + 1 = 05x - 8y - 12 = 05x + 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]] |
["*"] |
입출력 예 설명
입출력 예 #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인 경우 두 직선은 평행 또는 일치합니다.
✏️풀이
코드
import java.util.*;
class Solution {
public String[] solution(int[][] line) {
String[] answer = {};
List<long[]> list = new ArrayList<>();
// 최소 x, y값
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
// 최대 x, y값
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
for(int i = 0; i < line.length; i++) {
long a = line[i][0];
long b = line[i][1];
long e = line[i][2];
for(int j = i + 1; j < line.length; j++) {
long c = line[j][0];
long d = line[j][1];
long f = line[j][2];
// 분모
long down = a * d - b * c;
// 분자
long upX = b * f - e * d;
long upY = e * c - a * f;
if(down != 0) {
double x = upX / (double)down;
double y = upY / (double)down;
// 올림을 한 값이 x, y와 같다면
if(x == Math.ceil(x) && y == Math.ceil(y)) {
// list에 값을 저장
list.add(new long[]{(long)x, (long)y});
// min과 max를 비교
minX = Math.min(minX, (long)x);
minY = Math.min(minY, (long)y);
maxX = Math.max(maxX, (long)x);
maxY = Math.max(maxY, (long)y);
}
}
}
}
// 최소 사각형의 크기만큼 배열을 선언
boolean[][] boolTemp = new boolean[(int)(maxY - minY + 1)][(int)(maxX - minX + 1)];
// 별이 찍혀야하는 부분에 true를 저장
for(long[] temp: list) {
int x = (int)(temp[0] - minX);
int y = (int)(temp[1] - maxY);
boolTemp[Math.abs(y)][Math.abs(x)] = true;
}
answer = new String[boolTemp.length];
int index = 0;
// 줄별로 값을 확인
for(boolean[] bt : boolTemp) {
StringBuilder stb = new StringBuilder();
// 별이 찍혀야하는 부분에는 *을 아닌 부분에는 .을 저장
for(boolean b : bt) {
stb.append(b ? "*" : ".");
}
// 값을 저장
answer[index++] = stb.toString();
}
return answer;
}
}설명
단순 구현하여 진행하였다.
List 배열을 생성하여 값을 저장해준다. 이때 long[]을 사용해서 list를 만들어준다. 값을 계산했을 경우 int형을 벗어나기 때문이다.
최소 x, y의 값과 최대 x, y의 값을 저장해주기 위한 변수들을 선언해준다.
반복문을 사용하여 직선의 정보들을 받아온다. 문제의 참고사항을 토대로 변수 a, b, e를 설정해주고 해당 직선과의 교점을 구하기 위한 반복문을 진행한다. 이때 각각의 직선의 정보는 c, d, f이고 공식을 구하기 위해 분모와 분자를 각각 계산해준다.
분모가 0이 아닌 경우 계산이 가능하므로 0이 아닌 경우에 교점 x, y를 저장하고 해당 값을 올림했을 때 x, y와 같다면 list에 값을 저장하고 min값과 max값을 각각 비교해서 저장해준다.
모든 반복이 끝나면 사각형의 크기만큼 배열을 선언한다. list에 저장된 위치는 교점의 위치이며 해당 부분을 true로 저장해준다.
answer는 boolean형 배열의 길이만큼 배열을 선언해주며 줄별로 StringBuilder를 사용해서 값을 저장한다. true인지 false인지 확인을 하여 true라면 "*"을 false라면 "."을 저장해준다.
위의 모든 반복이 끝난뒤 저장된 answer 배열을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
코드의 길이가 길어져서 어려운 문제인 줄 알았으나 단순 수식의 계산을 통해 풀 수 있는 문제였다. 다만 자료형에 대해서 생각하지 못하고 풀다보니 오류가 나는 부분을 쉽게 알 수 없었다.. 자바에서 코테할 때 long형을 쓰는 것이 좋다고 한 이유를 이제야 알 것 같다.. 그래도 하나하나 신경쓰다보니 푸는 속도가 빨라진 것 같아서 좋다!
링크
