[프로그래머스/자바] 위클리 챌린지 10주차 교점에 별 만들기

사진 클릭시 문제로 이동

---

문제 설명

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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

---

입출력 예

line	esult
[[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]]	["*"]

 

---

참고 사항

Ax + By + E = 0
Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.

---

설명

마지막 참고사항을 이용해 교점을 구하고 해당 교점이 정수면 사용하면 된다.

코드

	import java.util.ArrayList;
	import java.util.HashSet;
	class PROGRAMMERS87377 {
	public String[] solution(int[][] line) {
	String[] answer;
	ArrayList<point> al = new ArrayList<>();
	HashSet<String> hs = new HashSet<>();
	for(int i = 0; i < line.length-1; i++){
	for(int j = i+1; j < line.length; j++){
	int a = line[i][0];
	int b = line[i][1];
	int e = line[i][2];
	int c = line[j][0];
	int d = line[j][1];
	int f = line[j][2];
	if (a*d - b*c == 0) continue;
	if(((double)b*f-e*d)%(a*d-b*c) != 0) continue;
	if(((double)e*c-a*f)%(a*d-b*c) != 0) continue;
	int x = (b*f-e*d)/(a*d-b*c);
	int y = (e*c-a*f)/(a*d-b*c);
	al.add(new point(x,y));
	}
	}
	int xMax = Integer.MIN_VALUE;
	int xMin = Integer.MAX_VALUE;
	int yMax = Integer.MIN_VALUE;
	int yMin = Integer.MAX_VALUE;
	for(point p : al) {
	int x = p.x;
	int y = p.y;
	xMax = Math.max(xMax, x);
	xMin = Math.min(xMin, x);
	yMax = Math.max(yMax, y);
	yMin = Math.min(yMin, y);
	hs.add(Integer.toString(x)+" "+Integer.toString(y));
	}
	int ind = 0;
	answer = new String[yMax-yMin+1];
	for(int j = yMax; yMin <= j; j--){
	String s = "";
	for(int i = xMin; i < xMax+1; i++){
	if(hs.contains(Integer.toString(i)+" "+Integer.toString(j))) s += "*";
	else s += ".";
	}
	answer[ind] = s;
	ind++;
	}
	return answer;
	}
	static class point {
	int x, y;
	point(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	}

view raw PROGRAMMERS87377.java hosted with ❤ by GitHub