직선들의 교점을 찾아 정리한 후 해당 교점들을 모두 포함할 수 있는 크기만큼만 출력하는 문제.
알고리즘상 어렵진 않으나 자료형 이슈가 있었다.
자료형을 잘못 작성한다면 한참 헤멜 수 있다.
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
class Star {
private long y;
private long x;
public Star(long y, long x) {
this.y = y;
this.x = x;
}
public long getY() {
return y;
}
public long getX() {
return x;
}
public String toString() {
return "(" + y + ", " + x + ")";
}
}
public String[] solution(int[][] line) {
double A, B, C, D, E, F, yf, xf;
long y, x, max_y = Long.MIN_VALUE, max_x = Long.MIN_VALUE, min_y = Long.MAX_VALUE, min_x = Long.MAX_VALUE;
List<Star> stars = new ArrayList<>();
for (int i = 0; i < line.length - 1; i++) {
A = line[i][0];
B = line[i][1];
E = line[i][2];
for (int j = i + 1; j < line.length; j++) {
C = line[j][0];
D = line[j][1];
F = line[j][2];
xf = (B * F - E * D) / (A * D - B * C);
yf = (E * C - A * F) / (A * D - B * C);
if (!(yf % 1 == 0 && xf % 1 == 0))
continue;
y = (long) yf;
x = (long) xf;
max_y = Math.max(y, max_y);
max_x = Math.max(x, max_x);
min_y = Math.min(y, min_y);
min_x = Math.min(x, min_x);
stars.add(new Star(y, x));
}
}
char[][] field = new char[(int)(max_y - min_y) + 1][(int)(max_x - min_x) + 1];
for (int i = 0; i < field.length; i++)
Arrays.fill(field[i], '.');
for (Star star: stars)
field[(int)(star.getY() - min_y)][(int)(star.getX() - min_x)] = '*';
String[] answer = new String[field.length];
for (int i = 0; i < field.length; i++)
answer[field.length - i - 1] = new String(field[i]);
return answer;
}
}
Star 해석 스킵. (toString()은 디버그하려고 구현, 없어도 무방)
double A, B, C, D, E, F, yf, xf;
long y, x, max_y = Long.MIN_VALUE, max_x = Long.MIN_VALUE, min_y = Long.MAX_VALUE, min_x = Long.MAX_VALUE;
문제 조건 중 A, B, C는 -100,000 이상 100,000 이하인 정수
가 있는데, 교점의 최댓값을 예측하자면 대략 100,000,000,000 (천억) 가까이 나온다. float, int형으로는 소화할 수 없음. 따라서 double, long으로 선언했다. (float 그대로 두고 풀면 29번만 틀리더라. 한참 찾았음)
for (int i = 0; i < line.length - 1; i++) {
A = line[i][0];
B = line[i][1];
E = line[i][2];
for (int j = i + 1; j < line.length; j++) {
C = line[j][0];
D = line[j][1];
F = line[j][2];
xf = (B * F - E * D) / (A * D - B * C);
yf = (E * C - A * F) / (A * D - B * C);
하나씩 가져와서 교점 계산. 참고 사항 제대로 안읽고 A, B, C로 선언 후 돌렸다가 교점이 죄다 이상하게 나왔었다. 잘 확인할 것.
if (!(yf % 1 == 0 && xf % 1 == 0))
continue;
y = (long) yf;
x = (long) xf;
max_y = Math.max(y, max_y);
max_x = Math.max(x, max_x);
min_y = Math.min(y, min_y);
min_x = Math.min(x, min_x);
stars.add(new Star(y, x));
yf, xf가 소수점이 있다면 스킵. 없으면 long으로 형변환하고 최대, 최소를 갱신. 그 후 리스트에 넣는다.
char[][] field = new char[(int)(max_y - min_y) + 1][(int)(max_x - min_x) + 1];
for (int i = 0; i < field.length; i++)
Arrays.fill(field[i], '.');
for (Star star: stars)
field[(int)(star.getY() - min_y)][(int)(star.getX() - min_x)] = '*';
String[] answer = new String[field.length];
for (int i = 0; i < field.length; i++)
answer[field.length - i - 1] = new String(field[i]);
return answer;
char 이차원 배열 만들고 최대 - 최소로 배열의 크기를 정한다.
배열 내 값을 다 .
으로 초기화 후 stars 리스트에서 하나씩 값을 뽑아 해당 자리를 *
로 만든다.
그 후 한줄씩 뽑아 String으로 만들고 반환. 이 때, 배열의 y좌표값과 그림의 y좌표값은 증감이 반대이므로 거꾸로 넣어준다.
def solution(line):
stars = set()
for i in range(len(line) - 1):
for j in range(i + 1, len(line)):
A, B, E = line[i]
C, D, F = line[j]
if A * D - B * C:
y = (E * C - A * F) / (A * D - B * C)
x = (B * F - E * D) / (A * D - B * C)
if not y % 1 and not x % 1:
y = int(y)
x = int(x)
stars.add((y, x))
stars = list(stars)
max_y, max_x = stars[0]
min_y, min_x = stars[0]
for y, x in stars:
if max_y < y:
max_y = y
if min_y > y:
min_y = y
if max_x < x:
max_x = x
if min_x > x:
min_x = x
row = max_y - min_y + 1
col = max_x - min_x + 1
sky = [['.'] * col for _ in range(row)]
for y, x in stars:
y -= max_y
x -= min_x
sky[-y][x] = '*'
return [''.join(s) for s in sky]
stars = set()
for i in range(len(line) - 1):
for j in range(i + 1, len(line)):
A, B, E = line[i]
C, D, F = line[j]
if A * D - B * C:
y = (E * C - A * F) / (A * D - B * C)
x = (B * F - E * D) / (A * D - B * C)
if not y % 1 and not x % 1:
y = int(y)
x = int(x)
stars.add((y, x))
교점을 구하고, 정수형으로 나타낼 수 있으면 set에 추가시킨다. (Java도 set 쓸걸.. 생각을 못했네)
for y, x in stars:
if max_y < y:
max_y = y
if min_y > y:
min_y = y
if max_x < x:
max_x = x
if min_x > x:
min_x = x
row = max_y - min_y + 1
col = max_x - min_x + 1
sky = [['.'] * col for _ in range(row)]
for y, x in stars:
y -= max_y
x -= min_x
sky[-y][x] = '*'
return [''.join(s) for s in sky]
최대, 최소 갱신
최적 좌표 크기 구함
.
으로 초기화하고, 처음부터 y방향 역좌표 계산해서 *
넣어준다.
그 후 join으로 문자열 만들고 반환.