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

#10주차 교점에 별 만들기

유형 : 수학 / 좌표

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

 

문제 풀이  

문제 참고를 확인하면 다음의 내용을 확인할 수 있다.

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

두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같다.

 

 

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

 

참고를 확인하지 않아도 해당 식을 구하는 방법은 간단하다. 두 방정식을 y로 정리하면 다음과 같다.

• 방정식 1 : y= -(A/B)x-(E/B)
• 방정식 2 : y= -(C/D)x-(F/D)

2를 1의 y에 대입하면, ((AD-BC)/BD)x = (BF-ED)/BD 

                                  x = (BF-ED)/(AD-BC) 이고,

반대로 x로 정리하면   y = (EC-AF)/(AD-BC) 로 정리할 수 있다.

 

따라서, 두 방정식의 교점은 ( (BF-ED)/(AD-BC), (EC-AF)/(AD-BC) ) 임을 알 수 있다.

 

해당 교점의 공통 분모 AD-BC가 0이 아닌경우와 정수가 아닌 경우를 제외하고 모든 교점을 구하면 된다. 모든 방정식은 1차 방정식이기 때문에 두 선의 교점이 2개 이상 존재할 수 없다. 평행할 경우를 제외하면 모두 1개의 교점을 갖는다. 해당 식으로 모든 교점을 구한 다음 별을 찍어 출력해주면 된다.

 

설계

a, b, c, d, e,f 의 범위는 주어지지 않았다. ad-bc, bf-ed, ec-af의 곱셈에서 int범위를 벗어나는 테케가 존재하므로 long타입으로 다뤄야 한다. 그 후에 구한 교점의 좌표는 -1000 ~1000 범위 안이므로 int로 형변환하여 사용하면 된다.

1. ax+by+e=0, cx+dy+f=0 두 방정식의 교점을 구한다.
2. ad-bc!=0이 아닌 경우, 교점이 존재한다.
   1. bf-ed와 ec-af를 ad-bc로 나눌 때 정수인 부분만 Set자료구조에 교점으로 저장한다.
      1. set.add(new Pos((int)xv/(int)v, (int)yv/(int)v));
3. 점이 찍히는 전체적인 사이즈를 구한다. getBorderSize(set.size());
   1. x좌표를 기준으로 오름차순을 하여, x좌표의 최대 최소값을 구한다. new XComp();
   2. y좌표를 기준으로 오름차순을 하여, y좌표의 최대 최소값을 구한다. new YComp();
4. 교점이 위치하는 부분은 '*', 아닌 부분은 '.'을 찍어 String배열에 저장한다.

 

풀이 코드 

import java.util.*;

public class Solution {
	static Set<Pos> set;
	static int minX, minY, maxX, maxY;
	public String[] solution(int[][] line) {
		set = new HashSet<>();
		for(int i=0; i<line.length-1; i++) {
			for(int j=i+1; j<line.length; j++) {
				long a = line[i][0], b = line[i][1], e = line[i][2];
				long c = line[j][0], d = line[j][1], f = line[j][2];
				long v = a*d-b*c;
				if(v!=0) {
					long xv = b*f-e*d;
					long yv = e*c-a*f;
					if(xv%v ==0 && yv%v ==0) {
						set.add(new Pos((int)xv/(int)v, (int)yv/(int)v));
					}
				}
			}
		}
		getBorderSize(set.size());
		String[] answer = new String[maxY-minY+1];
		StringBuilder sb;
		for(int i=maxY, idx=0; i>=minY; i--) {
			sb = new StringBuilder();
			for(int j=minX; j<=maxX; j++) {
				if(set.contains(new Pos(j,i))) sb.append("*");
				else sb.append(".");
			}
			answer[idx++] = sb.toString();
		}
		return answer;
	}
	
	static void getBorderSize(int size) {
		List<Pos> posList = new ArrayList<>(set);
		// x area
		Collections.sort(posList, new XComp());
		minX = posList.get(0).x; maxX = posList.get(size-1).x;
        
		// y area
		Collections.sort(posList, new YComp());
		minY = posList.get(0).y; maxY = posList.get(size-1).y;
	}
	
	static class Pos{
		int x;
		int y;
		
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + x;
			result = prime * result + y;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pos other = (Pos) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
	}
	
	static class XComp implements Comparator<Pos>{
		@Override
		public int compare(Pos o1, Pos o2) {
			return o1.x-o2.x;
		}
	}
	
	static class YComp implements Comparator<Pos>{
		@Override
		public int compare(Pos o1, Pos o2) {
			return o1.y-o2.y;
		}
	}
}