[Java] Programmers 2021 위클리 챌린지 10주차 - 교점에 별 만들기

[Java] Programmers 2021 위클리 챌린지 10주차 - 교점에 별 만들기

직선의 교점 중 정수가 되는 교점에 * 모양으로 표시하고, 이 별들을 포함하는 최소한의 사각형을 만들어서 출력하는 것이 문제이다.

먼저 정수가 되는 교점을 찾아야된다. 문제에서 친절하게 교점을 구하는 식을 알려주었다.

$$Ax + By + E = 0$$ $$Cx + Dy + F = 0$$

$$ x = {BF - ED \over AD -BC}, y = {EC - AF \over AD -BC}$$

이 식을 이용해서 교점을 구하면 된다. 단, AD-BC가 0인 경우에는 두직선이 평행하는 경우로 제외해준다.

그리고 나머지 연산을 이용해서 딱 나누어 떨어지는지를 체크하고, 정수의 교점만 찾는 것이기 때문에 딱 나누어 떨어지지 않으면 마찬가지로 제외해준다.

이렇게 구한 교점들을 배열에 넣어서 저장하고, 각각의 x와 y의 최대 최소값을 구한다.

좌표계에서 x방향으로의 증가는 2차원 배열에서 열로 값이 증가하는 것을 의미한다. 그래서 열의 index는 x - minX 가 된다.

반면 y방향으로의 증가는 행의 값의 감소를 의미한다. 그래서 행의 index는 maxY - y 가 된다.

미리 점(.)들로 answer를 채워 놓은 다음에 찾은 교점들을 순회하면서 점들을 별(*)로 바꿔주면 정답이 된다.

※주의 : a,b,c,d,e,f를 long으로 지정하자. 안그러면 int overflow가 발생하여 틀린 정답이 된다.

import java.util.ArrayList; import java.util.List; class Point { long x; long y; public Point(long x, long y) { this.x = x; this.y = y; } } class Solution { public String[] solution(int[][] line) { String[] answer = {}; int n = line.length; List points = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long a = line[i][0]; long b = line[i][1]; long e = line[i][2]; 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; } long x = bfed / adbc; long y = ecaf / adbc; points.add(new Point(x, y)); } } long minX = points.get(0).x; long minY = points.get(0).y; long maxX = points.get(0).x; long maxY = points.get(0).y; points.stream().forEach(a -> { System.out.println(a.x + " " + a.y); }); for (int i = 0; i < points.size(); i++) { Point p = points.get(i); minX = Math.min(minX, p.x); minY = Math.min(minY, p.y); maxX = Math.max(maxX, p.x); maxY = Math.max(maxY, p.y); } long width = maxX - minX + 1; long height = maxY - minY + 1; StringBuilder sb = new StringBuilder(); answer = new String[(int) height]; for (int i = 0; i < width; i++) { sb.append("."); } for (int i = 0; i < height; i++) { answer[i] = sb.toString(); } for (int k = 0; k < points.size(); k++) { Point p = points.get(k); long j = p.x - minX; long i = maxY - p.y; answer[(int) i] = answer[(int) i].substring(0, (int) j) + "*" + answer[(int) i].substring((int) (j + 1)); } return answer; } }

반응형

from http://blue-jay.tistory.com/87 by ccl(A) rewrite - 2021-10-14 01:27:47