프로그래머스 코딩테스트_도서실습
[코딩테스트_도서실습] 배열 - 교점에 별 만들기 - Lv2
러쉬봠
2023. 7. 8. 18:33
문제 설명
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의 세로(행) 길이는 2 이상 1,000 이하인 자연수입니다.
- line의 가로(열) 길이는 3입니다.
- line의 각 원소는 [A, B, C] 형태입니다.
- A, B, C는 -100,000 이상 100,000 이하인 정수입니다.
- 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않습니다.
- A = 0이면서 B = 0인 경우는 주어지지 않습니다.
- 정답은 1,000 * 1,000 크기 이내에서 표현됩니다.
- 별이 한 개 이상 그려지는 입력만 주어집니다.
입출력 예 설명
lineresult
| [[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]] | ["*"] |
나의 풀이
import java.util.*;
class Solution {
static long minx = Long.MAX_VALUE, miny =Long.MAX_VALUE;
static long maxx = Long.MIN_VALUE, maxy =Long.MIN_VALUE;
public String[] solution(int[][] line) {
String[] answer = {};
HashSet<Point> pSet = new HashSet<>();
long x,y;
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 adbc = a * d - b * c;
if(adbc == 0) continue;
long bfed = b*f-e*d;
if(bfed%adbc != 0) continue;
long ecaf = e*c-a*f;
if(ecaf%adbc != 0) continue;
x = bfed/adbc;
y = ecaf/adbc;
pSet.add(new Point(x,y));
minx = Math.min(minx,x);
miny = Math.min(miny,y);
maxx = Math.max(maxx,x);
maxy = Math.max(maxy,y);
}
}
long height = maxy - miny + 1;
long width = maxx - minx + 1;
answer = new String[(int)height];
StringBuilder sb = new StringBuilder();
for(int i =0; i < width; i ++){
sb.append(".");
}
Arrays.fill(answer, sb.toString());
long nx,ny;
for(Point p : pSet){
ny = maxy - p.y;
nx = p.x - minx;
answer[(int)ny] = answer[(int)ny].substring(0,(int)nx)+"*"+answer[(int)ny].substring((int)nx+1);
}
return answer;
}
public class Point{
long x;
long y;
public Point(long x, long y){
this.x = x;
this.y = y;
}
}
}다른사람 풀이 - 1
import java.util.*;
public class Solution {
public String[] solution(int[][] line) {
String[] answer = {};
List<long[]> list = new ArrayList<>();
long minX = Long.MAX_VALUE;
long maxX = Long.MIN_VALUE;
long minY = Long.MAX_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 xUp = b*f - e*d;
long xDown = a*d - b*c;
long yUp = e*c - a*f;
long yDown = a*d - b*c;
if(xDown != 0){
double x = xUp / (double)xDown;
double y = yUp / (double)yDown;
if(x == Math.ceil(x) && y == Math.ceil(y)){
list.add(new long[]{(long)x, (long)y});
minX = Math.min(minX, (long) x);
maxX = Math.max(maxX, (long) x);
minY = Math.min(minY, (long) y);
maxY = Math.max(maxY, (long) y);
}
}
}
}
boolean[][] answerTemp = new boolean[(int) (maxY- minY +1)][(int) (maxX - minX + 1)];
for (long[] ints : list) {
int x = (int) (ints[0] - minX);
int y = (int) (ints[1] - maxY);
answerTemp[Math.abs(y)][Math.abs(x)] = true;
}
answer = new String[answerTemp.length];
int i = 0;
for (boolean[] bs : answerTemp) {
StringBuilder sb = new StringBuilder();
for (boolean b : bs) {
if(b){
sb.append("*");
}else{
sb.append(".");
}
}
answer[i] = sb.toString();
i++;
}
return answer;
}
}다른사람 풀이 - 2
import java.util.*;
class Solution {
private static class Point {
long x;
long y;
public Point(long x, long y) {
this.x = x;
this.y = y;
}
}
List<Point> pointOfIntersection = new ArrayList<>();
Long minX = Long.MAX_VALUE;
Long minY = Long.MAX_VALUE;
Long maxX = Long.MIN_VALUE;
Long maxY = Long.MIN_VALUE;
public String[] solution(int[][] line) {
String[] answer = {};
for (int i = 0; i < line.length - 1; i++) {
for (int j = i + 1; j < line.length; j++) {
getPointOfIntersection(line[i], line[j]);
}
}
getMinPointAndMaxPoint();
long height = maxY - minY + 1;
long width = maxX - minX + 1;
answer = new String[(int) height];
boolean[][] board = new boolean[(int) height][(int) width];
for (Point point : pointOfIntersection) {
int x = (int) (point.x - minX);
int y = (int) (maxY - point.y);
board[y][x] = true;
}
int i = 0;
for (boolean[] booleans : board) {
StringBuilder sb = new StringBuilder();
for (boolean b : booleans) {
if (b) {
sb.append("*");
} else {
sb.append(".");
}
}
answer[i++] = sb.toString();
}
return answer;
}
private void getMinPointAndMaxPoint() {
for (Point point : pointOfIntersection) {
minX = Math.min(minX, point.x);
minY = Math.min(minY, point.y);
maxX = Math.max(maxX, point.x);
maxY = Math.max(maxY, point.y);
}
}
private void getPointOfIntersection(int[] A, int[] B) {
long a = A[0];
long b = A[1];
long c = B[0];
long d = B[1];
long e = A[2];
long f = B[2];
long denominator = a * d - b * c;
if (denominator == 0) {
return;
}
long xNumerator = b * f - e * d;
long yNumerator = e * c - a * f;
if (xNumerator % denominator != 0 || yNumerator % denominator != 0) {
return;
}
long x = xNumerator / denominator;
long y = yNumerator / denominator;
pointOfIntersection.add(new Point(x, y));
}
}출처 : https://arinnh.tistory.com/85