[프로그래머스(Programmers)][자바(java)] (Lv2) 10주차 - 교점에 별 만들기 <위클리 챌린지>

 

https://programmers.co.kr/learn/courses/30/lessons/87377

코딩테스트 연습 - 10주차

 

문제 풀이

 

import java.util.*;

public class Solution {
	
	class Dot {
		long x, y;
		public Dot(long x, long y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + (int) (x ^ (x >>> 32));
			result = prime * result + (int) (y ^ (y >>> 32));
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Dot other = (Dot) obj;
			if (x != other.x)
				return false;
			if (y != other.y)
				return false;
			return true;
		}
	}

	public String[] solution(int[][] line) {
		int nl = line.length, i, j, l[] = new int[2]; // nl : the num of lines
		long a, b, c, d, e, f, x, y, t; double tx, ty; // t : tmp, tx,ty : tmp_x/y
		HashSet<Dot> hs = new HashSet<>();
		for (i = 0; i < nl - 1; ++i) {
			for (j = i + 1; j < nl; ++j) {
				l = line[i]; a = l[0]; b = l[1]; e = l[2];
				l = line[j]; c = l[0]; d = l[1]; f = l[2];
				t = a * d - b * c;
				if (t == 0) continue;
				tx = (b * f - e * d) / (double) t;
				ty = (e * c - a * f) / (double) t;
				x = (long) tx; y = (long) ty; // Math.floor(tx)
				if (tx == x && ty == y)
					hs.add(new Dot(x, y));
			}
		}
		if (hs.size() == 0) return new String[] {""}; // the num of dots
		long x_min, x_max, y_min, y_max;
		x_min = y_min = Long.MAX_VALUE;
		x_max = y_max = Long.MIN_VALUE;
		for (Dot dot : hs) {
			x = dot.x; y = dot.y;
			x_min = x_min > x ? x : x_min;
			x_max = x_max < x ? x : x_max;
			y_min = y_min > y ? y : y_min;
			y_max = y_max < y ? y : y_max;
		}
		int w = (int)(x_max - x_min + 1), h = (int)(y_max - y_min + 1);
		boolean ans[][] = new boolean[h][w];
		for (Dot dot : hs)
			ans[(int)(h - Math.abs(dot.y - y_min) - 1)][(int)Math.abs(dot.x - x_min)] = true;
		String[] answer = new String[h];
		StringBuilder sb;
		for (i = 0; i < h; ++i) {
			sb = new StringBuilder();
			for (j = 0; j < w; ++j)
				sb.append(ans[i][j] ? '*' : '.');
			answer[i] = sb.toString();
		}
		return answer;
	}
}

( 교점( x, y 좌표 )들을 String 형태로 HashSet에 넣는 방법 )

import java.util.*;

public class Solution {

	public String[] solution(int[][] line) {
		int nl = line.length, i, j, l[] = new int[2];  // nl : the num of lines
		long a, b, c, d, e, f, x, y, t;  double tx, ty;  // t : tmp, tx,ty : tmp_x/y
		HashSet<String> hs = new HashSet<>();
		for (i = 0; i < nl - 1; ++i) {
			for (j = i + 1; j < nl; ++j) {
				l = line[i];  a = l[0]; b = l[1]; e = l[2];
				l = line[j];  c = l[0]; d = l[1]; f = l[2];
				t = a * d - b * c;  if (t == 0) continue;
				tx = (b * f - e * d) / (double) t;
				ty = (e * c - a * f) / (double) t;
				x = (long) tx;  // Math.floor(tx)
				y = (long) ty;
				if (tx == x && ty == y)
					hs.add(x + " " + y);
			}
		}
		int nd = hs.size();  if (nd == 0) return new String[] {""};  // nd : the num of dots
		long dots[][] = new long[nd][2];  i = 0;
		long x_min, x_max, y_min, y_max;
		x_min = y_min = Long.MAX_VALUE;
		x_max = y_max = Long.MIN_VALUE;
		StringTokenizer st;
		for (String s : hs) {
			st = new StringTokenizer(s);
			x = Long.parseLong(st.nextToken());
			y = Long.parseLong(st.nextToken());
			dots[i++] = new long[] { x, y };
			x_min = x_min > x ? x : x_min;
			x_max = x_max < x ? x : x_max;
			y_min = y_min > y ? y : y_min;
			y_max = y_max < y ? y : y_max;
		}
		int w = (int)(x_max - x_min + 1), h = (int)(y_max - y_min + 1);
		boolean ans[][] = new boolean[h][w];
		for (long[] dot : dots)
			ans[(h - (int)(dot[1] - y_min) - 1)][(int)(dot[0] - x_min)] = true;
		String[] answer = new String[h];
		StringBuilder sb;
		for (i = 0; i < h; ++i) {
			sb = new StringBuilder();
			for (j = 0; j < w; ++j)
				sb.append(ans[i][j] ? '*' : '.');
			answer[i] = sb.toString();
		}
		return answer;
	}
}

 

문제 밑에 제시된 공식을 이용하여 두 직선씩 모든 교점을 구함 ( 이 때 값의 overflow 주의 => long 변수에 담음 )

https://programmers.co.kr/learn/courses/30/lessons/87377

ex)

다음 5개의 직선이 주어졌을 경우

• 2x - y + 4 = 0
• -2x - y + 4 = 0
• -y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

모든 교점은 다음과 같다 ( 이 중 좌표값이 정수로만 구성된 교점만 취급 )

• {0.0, 4.0}
• {-1.5, 1.0}
• {-4.0, -4.0}
• {-2.0952380952380953, -0.19047619047619047}
• {1.5, 1.0}
• {2.0952380952380953, -0.19047619047619047}
• {4.0, -4.0}
• {4.0, 1.0}
• {-4.0, 1.0}
• {0.0, -1.5}

그 중 교점의 x, y 좌표가 모두 정수인 것들만 골라 HashSet hs 에 넣음 ( 중복 제거 )
교점들의 개수( hs.size() )가 0 보다 크면
x, y 좌표들의 각각의 최소값과 최대값을 구함 ( int x_min, x_max, y_min, y_max )

dots[i][0]  ( x 좌표 )	dots[i][1]  ( y 좌표 )
-4	-4
-4	1
0	4
4	-4
4	1

	x 좌표	y 좌표
최소값	-4	-4
최대값	4	4

좌표들이 위치하는 최소 영역만을 구성하기 위해 크기가 w * h 인 2차원 boolean ans [][] 배열 생성하여 위치 저장

	가로 ( int w )	세로 ( int h )
식	x_max - x_min + 1	y_max - y_min + 1
값	9	9

그 전에, 가로축과 세로축이 만나는 정중앙에 영점( 0, 0 )이 존재하는 좌표의 좌표값들을
왼쪽 상단 인덱스가 ( 0, 0 ) 인 2차원 배열에 저장하기 위해서 값 조정

• x 좌표값  ☞  dot.x - x_min
• y 좌표값  ☞  h - (  dot.y - y_min  ) - 1

x 좌표	y 좌표	배열의 i 인덱스	배열의 j 인덱스
-4	-4	8	0
-4	1	3	0
0	4	0	4
4	-4	8	8
4	1	3	8

배열 ans[i][j] 에 넣을 때는 조정한 x 값과 y 값의 반대 위치에 true 를 넣음
( 첫 번째 인덱스( i )에 y 값, 두 번째 인덱스( j )에 x 값 )

탐색하면서 true면 '*', false면 '.'를 차례로 넣고 문자열 생성 후 리턴