[알고리즘] 프로그래머스 교점에 별그리기 (레벨 2) / 자바 java 풀이

 

풀었던 문제를 다시 풀어보는 시간! 을 가졌는데 그래도 어렵다는 생각을 많이 했다. 주연님은 쉽다고 하던데 나는 왜 ....지? 🥹 "..........." ".....*....." "..........." "..........." ".*.......*." "..........." "..........." "..........." "..........." ".*.......*." "..........."

 

내가 풀었던 방법에 대해 풀이를 이제 꾸준히 적어보겠다!

 

📑 교점에 별 만들기

문제 설명

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	result
[[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인 경우 두 직선은 평행 또는 일치합니다.

 

✏️ 문제 해결 방법

우선 나는 문제에서 교점을 찾아 저장해야 한다 생각하였다. 

 

1. 교점 저장

 

주어지는 직선에 있어 교점이 몇 개가 생길지 모르기 때문에 교점을 확인하며 동적으로 x좌표, y좌표의 위치를 동시에 저장하고자 하였다. 

 

따라서, 교점을 저장하기 위한 자료 구조로 ArrayList<int[]> 를 만들어 주었다.

 

// 교점 저장하는 리스트
List<int[]> list = new ArrayList<>();

 

2. 교점 구하기

 

교점을 저장하기 위해서는 교점을 구해야 한다. 교점은 주어진 배열의 정보를 통해 쉽게 구할 수 있다. 

 

Ax + By + C = 0 이라고 할 때 배열에서는 차례대로 [A, B, C]를 나타내고 있다. 

 

두 직선은 평행하지 않으면 교점이 존재한다. (* 일치하는 경우는 없다고 제한사항에 나와있다.) 따라서, 평행하지 않은 경우를 제외하고 일차 방정식의 교점을 구하면 된다. 

 

교점을 구하는 식은 참고사항에도 나와있기 때문에 기억이 안 나더라도 괜찮다.

✅ 일차 방정식에서 교점 구하는 식

Ax + By + E = 0

Cx + Dy + F = 0

x = (B * F) - (E * D) / (A * D) - (B * C) 
y = (E * C) - (A * F) / (A * D) - (B * C)

* 평행한 경우는 (A * D) - (B * C) 가 0이 되는 경우 

위의 내용을 그대로 코드로 옮겨 적으면 된다.

for(int i = 0 ; i < line.length ; i++) {
	for(int j = 0 ; 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];
        
        long denom = (long)a*d - (long)b*c;
        if(denom != 0) {
        	long longX = (long) b*f - (long)e*f;
       		long longY = (long) e*c - (long)a*f;
        }
    }
}

 

3. list에 x, y 좌표 넣기

 

위에서 나온 이 x, y를 list에 넣어준다. 문제에서 요구하는 것과 같이 정수의 위치에만 별을 찍어야 한다. 따라서, 이 x좌표와 y좌표가 정수인지 판별을 해야 한다. 

 

정수인지 판별하는 방법은 쉽다. 나온 long형의 x좌표와 y 좌표를 denom으로 나누었을 때 나머지가 0 이면 정수일 것이고 아니면 정수가 아닌 실수일 것이다.

if(longX%denom == 0 && longY%denom == 0) {
	int x = (int)(longX/denom);
	int y = (int)(longY/denom);
	list.add(new int[]{x,y});
}

이 식을 추가로 작성해 준다.

 

4. 별 찍기

 

별을 찍는 부분이 조금 까다로웠다. ( * x좌표, y 좌표 생각하는 게 헷갈렸는데 그런 탓에 인덱스 에러가 나서 고생쓰 했다ㅋㅋ) 별은 교점 내에서 찍혀 나오도록 한다. 따라서, 교점 위치의 최솟값과 최댓값을 찾아야 한다. 

 

최솟값 최댓값을 찾기 위해 min 값에는 Integer.MAX_VALUE, max 값에는 Integer.MIN_VALUE를 둬서 list를 돌며 min값과 max 값을 찾아준다. 

 

x, y 축을 그려 생각해 보면 쉽다. 0의 위치도 있기 때문에 가로, 세로의 크기를 정할 때 max - min + 1을 해준다. 

 

그리고 별을 찍어줄 char[][] 2차원 배열을 만들어준다. 우선 모든 줄에 '.'으로 다 채워 준 뒤, list를 돌며 {x, y}에 해당하는 위치에 '*'을 찍어주는 것이다.

 

그리고 이 것을 다시 String[] 배열로 변환시켜 출력하면 된다. 

int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
        
for(int[] l : list) {
	int x = l[0];
	int y = l[1];
	minX = Math.min(minX, x);
	maxX = Math.max(maxX, x);
	minY = Math.min(minY, y);
	maxY = Math.max(maxY, y);
}

int width = maxX - minX + 1;
int height = maxY - minY + 1;
        
char[][] answer = new char[height][width];
        
for (char[] row : answer) {
	Arrays.fill(row, '.');
}
        
for(int[] l : list) {
	int x = l[0] - minX;
    int y = maxY - l[1];
	answer[y][x]= '*';
}
        
String[] result = new String[height];
        
for(int i = 0 ; i < height ; i++) {
	result[i] = new String(answer[i]);
}
        
        return result;

 

 

전체 코드

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        
        List<int[]> list = new ArrayList<>();
        
        for(int i = 0 ; i <line.length ; 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];
                
                long denom = (long)a*d - (long)b*c;
                if(denom != 0) {
                    long longX = (long) b*f - (long)e*d;
                    long longY = (long) e*c - (long)a*f;
                    
                    if(longX%denom == 0 && longY%denom == 0) {
                        int x = (int)(longX/denom);
                        int y = (int)(longY/denom);
                        
                        list.add(new int[]{x,y});
                    }
                }
            }
        }
        
        
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxY = Integer.MIN_VALUE;
        
        for(int[] l : list) {
            int x = l[0];
            int y = l[1];
            minX = Math.min(minX, x);
            maxX = Math.max(maxX, x);
            minY = Math.min(minY, y);
            maxY = Math.max(maxY, y);
        }
        int width = maxX - minX + 1;
        int height = maxY - minY + 1;
        
        
        char[][] answer = new char[height][width];
        
         for (char[] row : answer) {
            Arrays.fill(row, '.');
        }
        
        for(int[] l : list) {
            int x = l[0] - minX;
            int y = maxY - l[1];
            answer[y][x]= '*';
        }
        
        String[] result = new String[height];
        
        for(int i = 0 ; i < height ; i++) {
            result[i] = new String(answer[i]);
        }
        
        return result;

    }
    
}

 

🕸️ 문제 풀이 소감

이 문제는 풀면서 그렇게 까다롭지는 않았는데 위에서 말한 것처럼 x좌표와 y좌표 가 헷갈렸던 탓에 인덱스 에러가 너무 나서 머리를 한참 동안 쥐어뜯었다....ㅎㅎ

 

아무리 봐도 맞는 것 같은데 풀려야 할 것 같은데 안되길래 gpt한테 물어보고 싶었는데 gpt는 에러 상태라 들어가지 지도 않고 완전 완전 답답한 상태였는데 다음 날 다시 보니 x, y 좌표를 반대로 적어뒀더라....  너무 어이없었다 ....🫠 이런 실수를 하다니.....  진짜 이런 게 제일 안 보이는 듯하다 ㅜㅜㅜ

 

+) 블로깅 소감...

알고리즘 관련글을...이렇게 열심히 쓰다 보면... 내가 꾸준히 쓸 수 있을지는 모르겠다는 생각ㅋㅋㅋ

조금 덜 열심히 써 봐야겠다... 풀이는 간단히 그리고 고 전체 코드에 설명을 덧붙이 던 지 해야겠다.