문제 설명
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
좌표 평면 위에 그리면 아래 그림과 같습니다.
RisingStarGraphBox.jpg
이때, 모든 교점의 좌표는 (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)입니다.
만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.
RisingStarGraphStar.jpg
위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은 *, 빈 공간(격자선이 교차하는 지점)은 .으로 표현하면 다음과 같습니다.
"..........."
".........."
"..........."
"..........."
"........."
"..........."
"..........."
"..........."
"..........."
"........*."
"..........."
이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.
따라서 정답은
"........"
"........."
"........."
"......."
"........."
"........."
"........."
"........."
".......*"
입니다.
직선 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 크기 이내에서 표현됩니다.
별이 한 개 이상 그려지는 입력만 주어집니다.
전체코드
import java.util.ArrayList;
import java.util.List;
class Solution {
// 1
private static class Point {
public final long x, y;
private Point(long x, long y) {
this.x = x;
this.y = y;
}
}
// 2
public static Point intersection(long a1, long b1, long c1, long a2, long b2, long c2) {
double x = (double)(b1*c2 - b2*c1) / (a1*b2 - a2*b1);
double y = (double)(a2*c1 - a1*c2) / (a1*b2 - a2*b1);
if((x % 1 != 0) || (y % 1 != 0)) {
return null;
}
return new Point((long)x, (long)y);
}
public String[] solution(int[][] line) {
List<Point> points = new ArrayList<>();
// 3
for(int i = 0; i < line.length; i++) {
for(int j = i+1; j <line.length; j++) {
Point intersection = intersection(line[i][0], line[i][1], line[i][2], line[j][0], line[j][1], line[j][2]);
if(intersection != null) {
points.add(intersection);
}
}
}
// 4
long maxX = Long.MIN_VALUE;
long maxY = Long.MIN_VALUE;
long minX = Long.MAX_VALUE;
long minY = Long.MAX_VALUE;
for(int i = 0; i <points.size(); i++) {
maxX = Math.max(maxX, points.get(i).x);
minX = Math.min(minX, points.get(i).x);
maxY = Math.max(maxY, points.get(i).y);
minY = Math.min(minY, points.get(i).y);
}
// 5
int xLength = (int)(maxX - minX + 1);
int yLength = (int)(maxY - minY + 1);
char[][] map = new char[yLength][xLength];
// 6
for(int i = 0; i < yLength; i++) {
for(int j = 0; j < xLength; j++) {
map[i][j] = '.';
}
}
for(int i = 0; i <points.size(); i++) {
int x = (int)(points.get(i).x - minX);
int y = (int)(maxY-points.get(i).y);
map[y][x] = '*';
}
String[] answer = new String[map.length];
for(int i = 0; i < answer.length; i++) {
answer[i] = new String(map[i]);
}
return answer;
}
}풀이
1. 좌표 문제가 나타나면 좌표 클래스를 활용하자
public static class Point {
public final long x, y;
private Point(long x, long y) {
this.x = x;
this.y = y;
}
}
x, y 의 값을 한번에 받을 수 있는 Point 클래스를 만들어줍시다.
2. 교차점을 구할 수 있는 함수를 만들어줍니다.
Ax + By + C = 0 을 활용해서 교차되는 x 와 y를 구할 수 있는 식을 작성합니다.
이건 직접 손으로 풀어보면 나오지만
A1x + B1y + C1 = 0 과 A2x + B2y + C2 = 0 을
x = (나머지) 이런식으로 정리해서 두 식을 비교하면 y = (a2c1 - a1c2) / (a1b2 - a2b1) 이 나옵니다.
반대로
x = (나머지) 이런식으로 정리해서 두 식을 비교하면 x = (b1c2 - b2c1) / (a1b2 - a2b1) 이 나옵니다.
그래서 만약 정수가 아니면 null이 반환되도록 합니다.
3.
points 라는 Point타입 배열에
중첩반복문을 통해 정수 교차점을 모두 저장합니다.
4.
문제에서 모든 별을 포함하는 최소사각형을 리턴하라고 했으므로
x와 y의 최대 최소 값을 구해 2차원 배열을 만들어야 합니다.
저는 points 배열을 돌면서 x와 y의 최대 최소 값을 구했습니다.
5.
혼동될 수 있는 부분입니다.
xLength 는 이차원 배열에서 [x][] 부분이 아니라
[][x] 부분입니다. 즉 함수 그래프에서 가로축에 해당되는 부분을 의미하므로 [][xLength]라고 대입해야 합니다.
또한 (maxX - minX + 1) 처럼 1을 더해줘야지 크기를 구할 수 있습니다.
1을 더하지 않으면 outbounds 에러가 출력됩니다.
그리고 int로 캐스팅 하지 않으면 map이라는 2차원 배열을 만들 수가 없습니다.
6.
여기서 가장 어려운 부분은
for(int i = 0; i <points.size(); i++) {
int x = (int)(points.get(i).x - minX);
int y = (int)(maxY-points.get(i).y);
map[y][x] = '*';
}이 부분입니다.
수학에서 나타내는 일반 좌표와
우리가 만들어야 할 2차원 배열에서 좌표는 다르게 나타납니다.
즉 수학에서 (0, 0) 점은 2차원 배열에서 정답마다 다르게 표현된다는 것이죠.
그렇다면 어떻게 해야 할까요?
일반 함수에서 2차원 배열로 바뀔 때
y축은 뒤집혀집니다. 이 말은 y의 최대값이 2차원 배열에선 0이 되어야 한다는 말입니다.
따라서 int y = (int)(maxY-points.get(i).y); 라고 할 수 있습니다.
x의 경우 현재 x의 값에서 x의 최소값을 빼면 2차원 배열에서의 x 위치가 됩니다. 왜냐하면 2차원 배열에서 가로 세로는 x와 y의 최대 최소 값으로 정해지기 때문입니다.
이를 활용해 * 을 찍어주면 되겠습니다!
참고자료[프로그래머스 코딩테스트 문제 풀이 전략 : 자바편]
