무수히 많은 교점이 생기는 경우는 없음. - 두 직선의 관계는 만나지 않음, 1개의 교점이 생김, 무수히 많은 교점이 생기는 경우 세가지이다.
시간 복잡도 고려 -> 입력량은 1000 이하, O(N^3) 이상이 될 경우 1억번의 연산 -> 시간초과될 확률 있음.
입력 수 범위는 -100,000 ~ 100,000으로 주어짐 - 입력의 덧셈, 뺄셈, 나눗셈 연산만 하게 될 경우 int면 충분 - 입력의 곱셈 연산을 할 경우 long 자료형이 필요함
4. 참고사항 파악
Ax + By + E = 0 Cx + Dy + F = 0
두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다. 또, AD - BC = 0인 경우 두 직선은 평행 또는 일치합니다.
두 직선이 한 개의 교점을 갖는 경우와 만나지 않는지의 여부를 확인해야 함.
한 개의 교점을 가지는 경우 위의 식을 통해 교점의 좌표를 얻어낼 수 있음.
교점을 가지지 않거나 무수히 많은 교점을 가지는 경우, x, y의 값이 INF가 될 것이다. -> 직선이 평행하거나 일치하는 경우
5. 출력형태 파악
위의 그림을 문자열로 나타낼 때, 별이 그려진 부분은*, 빈 공간(격자선이 교차하는 지점)은.으로 표현하면 다음과 같습니다.
이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.
출력형태는 String[]
모든 교점을 포함시키기 위한 최소 격자 크기를 정해야 함. - 교점의 (x,y)좌표의 최댓값, 최소값을 이용하여 격자의 크기를 정할 수 있음.
풀이과정 도출
1. 모든 직선 쌍에 대해서 아래의 과정을 행함
교점 좌표 구하기 : 교점 도출 식을 통해 (x, y)좌표가 나온다면 AND x, y가 정수라면 교점 리스트에 저장
교점 리스트에 저장할 때, x좌표, y좌표 각각의 최대값, 최소값을 갱신함
2. 출력을 위해서 격자 문자열을 생성한 후, 출력 포멧으로 반환
최대값, 최소값을 이용하여 격자의 크기를 결정 - 너비 : max X - min X + 1 - 높이 : max Y - min Y + 1
격자에 교점 리스트에 포함된 좌표일 경우 *를, 아닐 경우 .를 차례로 갱신
문자열 배열로 표현 후 반환
문제풀이
1. 모든 직선 쌍에 대해서 아래의 과정을 행함
교점 좌표 구하기 : 교점 도출 식을 통해 (x, y)좌표가 나온다면 AND x, y가 정수라면 교점 리스트에 저장
교점 리스트에 저장할 때, x좌표, y좌표 각각의 최대값, 최소값을 갱신함
(1) 리팩토링 이전
아래 과정은 코드 리팩토링 하기 이전 단계이다.
1-1. 입력에 대한 순회
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인
//3, 4. X,Y 교점 구하기
//5. x, y 최대/최솟값 갱신
//6. 찾은 교점 리스트에 추가
}
}
}
먼저 모든 직선 쌍에 대해서 교점의 여부를 검사하기 위해서 입력에 대한 순회를 한다.
순서는 중요하지 않고, 자기 자신과의 쌍을 맺지 않으므로 다음과 같이 입력을 순회한다.(nC2의 조합) - [A, B, C, D, E]의 직선이 있다면, A는 B, C, D, E와의 교점 여부를, 다음 B는 C, D, E와의 교점 여부만 검사하면 된다.
각 직선의 x 계수, y 계수, 상수항을 추출해 둔다.
1-2. 평행 또는 일치여부 확인하기
//2.평행 혹은 일치여부 확인하기
public boolean isParallelOrEqual(int x1, int x2, int y1, int y2){
if(((x1 * y2) - (x2 * y1)) == 0){
return true;
}
else{
return false;
}
}
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인
boolean isNotExistPoint = this.isParallelOrEqual(x1, x2, y1, y2);
if(!isNotExistPoint){
//3, 4. X,Y 교점 구하기
//5. x, y 최대/최솟값 갱신
//6. 찾은 교점 리스트에 추가
}
}
}
}
우선 교점이 존재하지 않는 경우를 판단한다. 만약 평행하거나 일치하는 경우라면 교점을 구하는 과정을 생략하고 넘어간다.
1-3. 두 직선의 교점 X, Y 좌표 구하기
//3. 교점 X 구하기
public Integer findX(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
//4. 교점 Y
public Integer findY(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
다음은 x 계수, y 계수, 상수항을 바탕으로 두 직선의 X, Y 좌표를 도출하는 메서드이다.
마지막 리턴 과정에서 정수임을 확인한 후, 정수가 아니라면 null을 반환한다.
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인
boolean isNotExistPoint = this.isParallelOrEqual(x1, x2, y1, y2);
if(!isNotExistPoint){
//3, 4. X,Y 교점 구하기
Integer findX = this.findX(x1, x2, c1, c2, y1, y2);
Integer findY = this.findY(x1, x2, c1, c2, y1, y2);
if(findX != null && findY != null){ //만약 교점이 둘 다 정수라면
//5. x, y 최대/최솟값 갱신
//6. 찾은 교점 리스트에 추가
}
}
}
}
}
두 직선의 교점을 구하는 로직을 순회 과정에 추가시킨다.
두 교점이 모두 정수라면(null이 아니라면), 좌표들의 최댓값, 최솟값을 갱신시키고, 교점 리스트에 추가시키는 과정을 거치면 된다.
1-4. 좌표 최댓값, 최솟값 갱신 및 교점 리스트에 추가하기
public int minX = Integer.MAX_VALUE;
public int minY = Integer.MAX_VALUE;
public int maxX = Integer.MIN_VALUE;
public int maxY = Integer.MIN_VALUE;
//5. 좌표 최댓값, 최소값 갱신
public void changeMaxAndMin(int x, int y){
if(x < minX){
minX = x;
}
if(x > maxX){
maxX = x;
}
if(y < minY){
minY = y;
}
if(y > maxY){
maxY = y;
}
}
//교점 리스트
List<int[]> points = new ArrayList<>();
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인
boolean isNotExistPoint = this.isParallelOrEqual(x1, x2, y1, y2);
if(!isNotExistPoint){
//3, 4. X,Y 교점 구하기
Integer findX = this.findX(x1, x2, c1, c2, y1, y2);
Integer findY = this.findY(x1, x2, c1, c2, y1, y2);
if(findX != null && findY != null){ //만약 교점이 둘 다 정수라면
this.changeMaxAndMin((int)findX, (int)findY); //5. x, y 최대/최솟값 갱신
int[] point = {(int)findX, (int)findY};
this.points.add(point); //6. 찾은 교점 리스트에 추가
}
}
}
}
}
찾아낸 교점들을 저장할 ArrayList를 선언한다.
교점의 표현은 [1, 2]와 같이 int[]형을 사용할 것이다. -> 객체지향의 특성을 살려 Class 형태를 사용하는 것이 좋으나 단순 x,y좌표이므로 배열로 나타냈다.
격자를 그리기 위해 필요한 교점들 리스트와 좌표의 최대값, 최소값을 순회 시 마다 갱신해준다.
현재까지의 코드
import java.util.*;
class Solution {
public int minX = Integer.MAX_VALUE;
public int minY = Integer.MAX_VALUE;
public int maxX = Integer.MIN_VALUE;
public int maxY = Integer.MIN_VALUE;
//교점
List<int[]> points = new ArrayList<>();
//2.평행 혹은 일치여부 확인하기
public boolean isParallelOrEqual(int x1, int x2, int y1, int y2){
if(((x1 * y2) - (x2 * y1)) == 0){
return true;
}
else{
return false;
}
}
//3. 교점 X 구하기
public Integer findX(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
//4. 교점 Y
public Integer findY(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
//5. 좌표 최댓값, 최소값 갱신
public void changeMaxAndMin(int x, int y){
if(x < minX){
minX = x;
}
if(x > maxX){
maxX = x;
}
if(y < minY){
minY = y;
}
if(y > maxY){
maxY = y;
}
}
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인
boolean isNotExistPoint = this.isParallelOrEqual(x1, x2, y1, y2);
if(!isNotExistPoint){
//3, 4. X,Y 교점 구하기
Integer findX = this.findX(x1, x2, c1, c2, y1, y2);
Integer findY = this.findY(x1, x2, c1, c2, y1, y2);
if(findX != null && findY != null){ //만약 교점이 둘 다 정수라면
this.changeMaxAndMin((int)findX, (int)findY); //5. x, y 최대/최솟값 갱신
int[] point = {(int)findX, (int)findY};
this.points.add(point); //6. 찾은 교점 리스트에 추가
}
}
}
}
//7. 좌표 문자열 만들기
}
}
(1) 리팩토링 이후
위의 코드는 일부 테스트 케이스를 제외하고는 정상적으로 돌아간다.
하지만 일부 테스트 케이스 실패가 있었으며, 과정을 간소화할 수 있다.
class Solution {
public long minX = Long.MAX_VALUE;
public long minY = Long.MAX_VALUE;
public long maxX = Long.MIN_VALUE;
public long maxY = Long.MIN_VALUE;
//교점
List<long[]> points = new ArrayList<>();
//3. 교점 X
public Long findX(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
//4. 교점 Y
public Long findY(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
//5. 좌표 최댓값, 최소값 갱신
public void changeMaxAndMin(long x, long y){
if(x < minX){
minX = x;
}
if(x > maxX){
maxX = x;
}
if(y < minY){
minY = y;
}
if(y > maxY){
maxY = y;
}
}
//입력 = [[x, y, 상수]]
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인(X)
//3, 4. X,Y 교점 구하기
Long findX = this.findX(x1, x2, c1, c2, y1, y2);
Long findY = this.findY(x1, x2, c1, c2, y1, y2);
if(findX != null && findY != null){ //만약 교점이 둘 다 정수라면
this.changeMaxAndMin(findX, findY); //5. x, y 최대/최솟값 갱신
long[] point = {findX, findY};
this.points.add(point); //6. 찾은 교점 리스트에 추가
}
}
}
//7. 좌표 문자열 만들기
}
}
다음은 아래의 개선사항이 이루어진 소스코드이다.
평행/일치 확인 여부 로직을 교점을 구할 때 함께 확인하도록 변경 -> "2. 평행, 일치여부 확인 과정"의 계산을 없애서 로직 간소화
교점 계산 시 오버플로우 발생 -> 계산을 위해서 자료형을 Long으로 변경
//3. 교점 X
public Long findX(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
//4. 교점 Y
public Long findY(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
/*
//3. 교점 X 구하기
public Integer findX(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
//4. 교점 Y
public Integer findY(int x1, int x2, int c1, int c2, int y1, int y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result == (int)result) ? (int)result : null;
}
*/
평행/일치 확인 여부 로직을 교점을 구할 때 함께 확인하도록 변경
평행/일치 확인 여부 로직을 교점을 구할 때 함께 확인하도록 변경하기 위해서 교점을 구하는 로직을 변경하였다.
평행/일치 여부 확인 식은 (x1 * y2) - (y1 * x2)가 0인 경우로 확인할 수 있다고 하였다. 해당 식은 교점을 구하는 식에서의 분모에 해당한다. 따라서 굳이 평행/일치 여부 확인을 하지 않고 교점을 구할 때 한번에 확인이 가능하다.
마지막에 정수 판별 시 분모가 0인 경우 result는 INF가 된다. 따라서, int형으로 형변환하여 확인하는 것이 불가능하다. 그래서 모듈러 연산을 통해 정수를 판별하도록 바꿔준다.
교점 계산 시 오버플로우 발생 -> 계산을 위해서 자료형을 Long으로 변경
문제에서 X,Y의 계수 및 상수항의 범위는 -100,000 ~ 100,000으로 주어졌다. 이는 int형으로 충분히 표현 가능한 자료형이다. 그렇지만 교점을 구하는 가정에서 두개의 계수 혹은 상수의 곱셈 연산이 이루어진다. 따라서 최댓값일 경우 10,000,000,000 > 2,147,483,647로 int로 표현이 불가능해진다. 따라서 자료형을 long으로 바꾸어 주었다.
2. 출력을 위해서 격자 문자열을 생성한 후, 출력 포멧으로 반환
최대값, 최소값을 이용하여 격자의 크기를 결정 - 너비 : max X - min X + 1 - 높이 : max Y - min Y + 1
격자에 교점 리스트에 포함된 좌표일 경우 *를, 아닐 경우 .를 차례로 갱신
문자열 배열로 표현 후 반환
(2) 리팩토링 이전
아래 과정은 코드 리팩토링 하기 이전 단계이다.
public int minX = Integer.MAX_VALUE;
public int minY = Integer.MAX_VALUE;
public int maxX = Integer.MIN_VALUE;
public int maxY = Integer.MIN_VALUE;
//교점
List<int[]> points = new ArrayList<>();
//7. 좌표 문자열 만들기
public String[] makeStar(){
int length = maxY - minY + 1;
String[] answer = new String[length];
boolean contains = false;
for(int j = this.maxY; j >= minY; j--){
String s = "";
for(int i = this.minX; i <= maxX; i++){
int[] point = {i, j};
contains = false;
for(int[] p : points){
if (Arrays.equals(p, point)) {
contains = true;
break;
}
}
if(contains){
s += "*";
}
else{
s += ".";
}
}
answer[this.maxY - j] = s;
}
return answer;
}
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
//...
}
}
//7. 좌표 문자열 만들기
String[] answer = this.makeStar();
return answer;
}
문자열 배열의 크기(세로)는 maxY - minY + 1에 해당한다.
격자는 2차원 형태이다. 따라서 x좌표와 y좌표에 대한 2중 반복문 수행을 통해 출력값을 생성한다. - 1) 열 생성 반복 -> 1행 생성 : x좌표에 대한 순회를 통해서 '.' 또는 '*'로 이루어진 문자열 하나를 생성한다. - 2) 행 생성 반복 -> 격자 생성 : y좌표에 대한 순회를 통해서 1)의 문자열들을 반복하여 생성한다.
격자에 좌표를 표현해야 하는 경우 다음 사항을 유의해야 한다. - 왼쪽 위부터, x좌표는 작은 순서대로, y좌표는 큰 순서대로 표현되어야 한다. - 따라서 y는 max값을 시작으로, x는 min값을 시작으로 2중 반복문을 수행해야 한다. * y좌표는 큰 순서대로 표현되어야 한다고 했다. 한 행이 생성되었을 때, 결과 배열에 대입할 때 answer[j]에 대입하는 것이 아니라,answer[this.maxY - j]에 대입
반복문 수행 중, 해당 좌표가 point에 대해 속해 있는지를 판별하여 '*' 혹은 '.'를 문자열에 추가한다. - 해당 경우는 최악의 경우 [X축 너비 * Y축 높이 * 교점의 개수] 만큼의 연산을 추가로 실행해야한다는 뜻이다. 연산을 줄이기 위해서 리팩토링을 실행할 것이다.
(2) 리팩토링 이후
class Solution {
public long minX = Long.MAX_VALUE;
public long minY = Long.MAX_VALUE;
public long maxX = Long.MIN_VALUE;
public long maxY = Long.MIN_VALUE;
//교점
List<long[]> points = new ArrayList<>();
public String[] makeStar(){
int width = (int)(maxX - minX + 1);
int height = (int)(maxY - minY + 1);
char[][] answer = new char[height][width];
for(char[] row: answer){
Arrays.fill(row, '.');
}
for(long[] point: points){
answer[(int)(maxY - point[1])][(int)(point[0] - minX)] = '*';
}
String[] result = new String[answer.length];
for(int i = 0; i < answer.length; i++){
result[i] = new String(answer[i]);
}
return result;
}
//입력 = [[x, y, 상수]]
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
//...
}
}
//7. 좌표 문자열 만들기
String[] answer = this.makeStar();
return answer;
}
}
'*' 혹은 '.'을 입력을 판단하기 위해서 실행되는 로직의 최악의 경우 [X축 너비 * Y축 높이 * 교점의 개수] 만큼의 연산을 추가로 실행해야 했던 위 코드를 갱신할 수 있다.
변경된 로직은 우선 모든 원소들을 '.'으로 채운 후, points의 교점 리스트의 원소에 대해서만 해당 좌표를 찾아 갱신하도록 하였다. 해당 방법은 교점의 개수만큼의 연산만 수행하면 된다.
char[][]형의 2차원 배열 대입 방법 : answer[(int)(maxY - point[1])][(int)(point[0] - minX)] = '*'; - 항상 2차원 배열은 Array[행][열]로 표현된다는 것을 유의하자. -> answer[y][x]로 이루어져야 한다. - point의 인덱스는 말그대로 수학적 좌표이고, answer의 인덱스는 원래 좌표가 최댓값과 최소값을 기반으로 조정된 것임을 유의 * maxY와 maxX를 이용하여 해당 좌표들 간의 차이를 보정할 수 있다. * 일반식을 처음부터 도출하기 어렵다면, 예시 케이스 두가지 정도를 생각하여, 일반식을 도출하는 방법을 활용하면 좋다.
최종 소스코드
class Solution {
public long minX = Long.MAX_VALUE;
public long minY = Long.MAX_VALUE;
public long maxX = Long.MIN_VALUE;
public long maxY = Long.MIN_VALUE;
//교점
List<long[]> points = new ArrayList<>();
//3. 교점 X
public Long findX(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(y1 * c2) - (c1 * y2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
//4. 교점 Y
public Long findY(long x1, long x2, long c1, long c2, long y1, long y2){
double result = ((double)(c1 * x2) - (x1 * c2)) / ((x1 * y2) - (y1 * x2));
return (result % 1 == 0) ? (long)result : null;
}
//5. 좌표 최댓값, 최소값 갱신
public void changeMaxAndMin(long x, long y){
if(x < minX){
minX = x;
}
if(x > maxX){
maxX = x;
}
if(y < minY){
minY = y;
}
if(y > maxY){
maxY = y;
}
}
public String[] makeStar(){
int width = (int)(maxX - minX + 1);
int height = (int)(maxY - minY + 1);
char[][] answer = new char[height][width];
for(char[] row: answer){
Arrays.fill(row, '.');
}
for(long[] point: points){
answer[(int)(maxY - point[1])][(int)(point[0] - minX)] = '*';
}
String[] result = new String[answer.length];
for(int i = 0; i < answer.length; i++){
result[i] = new String(answer[i]);
}
return result;
}
public String[] solution(int[][] line) {
//1. 입력에 대한 순회
for(int i = 0; i < line.length; i++){
for(int j = i + 1; j < line.length; j++){
int x1 = line[i][0];
int x2 = line[j][0];
int y1 = line[i][1];
int y2 = line[j][1];
int c1 = line[i][2];
int c2 = line[j][2];
//2. 평행, 일치여부 확인(X)
//3, 4. X,Y 교점 구하기
Long findX = this.findX(x1, x2, c1, c2, y1, y2);
Long findY = this.findY(x1, x2, c1, c2, y1, y2);
if(findX != null && findY != null){ //만약 교점이 둘 다 정수라면
this.changeMaxAndMin(findX, findY); //5. x, y 최대/최솟값 갱신
long[] point = {findX, findY};
this.points.add(point); //6. 찾은 교점 리스트에 추가
}
}
}
//7. 좌표 문자열 만들기
String[] answer = this.makeStar();
return answer;
}
}
