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

문제 링크

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

프로그래머스

 

 

코딩테스트 연습 > 위클리 챌린지 > 교점에 별 만들기

 

 

문제 설명

 

 

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

 

---

 

입출력 예 설명

 

입출력 예 #1

 

문제 예시와 같습니다.

 

 

입출력 예 #2

 

직선 y = 1, x = 1, x = -1는 다음과 같습니다.

 

 

(-1, 1), (1, 1) 에서 교점이 발생합니다.

 

따라서 정답은

 

"*.*"  

 

입니다.

 

 

입출력 예 #3

 

직선 y = x, y = 2x는 다음과 같습니다.

 

 

(0, 0) 에서 교점이 발생합니다.

 

따라서 정답은

 

"*"  

 

입니다.

 

 

입출력 예 #4

 

직선 y = x, y = 2x, y = 4x는 다음과 같습니다.

 

 

(0, 0) 에서 교점이 발생합니다.

 

따라서 정답은

 

"*"

 

입니다.

 

---

참고 사항

 

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

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

 

 

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

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        
        Set<Point> set = new HashSet<>();
        
        long minX = Long.MAX_VALUE;
        long maxX = Long.MIN_VALUE;
        long minY = Long.MAX_VALUE;
        long maxY = Long.MIN_VALUE;
            
        for(int i=0; i<line.length-1; i++) {
            long a = line[i][0];
            long b = line[i][1];
            long e = line[i][2];
            
            for(int j=i+1; j<line.length; j++) {
                long c = line[j][0];
                long d = line[j][1];
                long f = line[j][2];
                
                if(a*d - b*c == 0) continue; // 평행 or 일치
                
                if((b*f - e*d) % (a*d - b*c) != 0) continue; // x좌표 정수 아닌 경우
                if((e*c - a*f) % (a*d - b*c) != 0) continue; // y좌표 정수 아닌 경우
                
                long x = (b*f - e*d) / (a*d - b*c);
                long y = (e*c - a*f) / (a*d - b*c);
                
                set.add(new Point(x, y));
                
                minX = Math.min(minX, x);
                maxX = Math.max(maxX, x);
                minY = Math.min(minY, y);
                maxY = Math.max(maxY, y);
            }
            
        }
        
        long width = maxX - minX + 1;
        long height = maxY - minY + 1;
        
        String[] answer = new String[(int) height];
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<width; i++) {
            sb.append(".");
        }
        
        for(int i=0; i<height; i++) {
            answer[i] = String.valueOf(sb);
        }
        
        for(Point p : set) {
            long nx= p.x-minX;
            long ny= maxY-p.y;
            
            answer[(int) ny] = answer[(int) ny].substring(0, (int) nx) + "*" + answer[(int) ny].substring((int) nx+1);
        }
        
        return answer;
    }
                                       
    public class Point{
        long x;
        long y;
        
        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }                   
}

 

풀이

1. 모든 직선의 교점을 구하고 그 교점들 중에서 최소 x좌표와 최대 x좌표, 최소 y좌표와 최대 y좌표를 구해 해당 직사각형 크기만큼 "."으로 채운 후 교점들의 좌표에 해당하는 자리를 "*"로 변환하여 리턴한다.
2. 우선 좌표 x, y를 가진 객체를 사용하기해 Point 클래스를 만들고 직선들의 교점들을 담기 위해 Point를 선업 타입으로 하는 Set을 생성한다. 혹 교점이 겹칠 수 있기때문에 중복된 데이터를 가지지 않는 Set을 선택한다.
3. 그리고 최소 x좌표와 최대 x좌표, 최소 y좌표와 최대 y좌표를 기억하기 위한 변수를 선언한다.
4.  이제 직선들의 모든 교점을 구해 Set에 담아준다. line을 이중 for문을 통해 모든 교점을 구한다.
   교점을 구할 때는 두 직선이 평행 or 일치 하는 경우를 제외해주고 문제에 주어진 것처럼 교점의 x좌표, y좌표가 정수가 아닌 것도 제외해준다. 두 직선이 평행 or 일치하는 경우와 x좌표, y좌표를 구하는 방법이 문제 참고 사항에 주어졌으므로 이용하여 구하도록 한다.
5. 이렇게 제외 조건을 고려하여 교점들을 구해서 Set에 담아주고 최대, 최소 x와 y좌표를 저장한다.
6. 이제 Set에 교점들을 다 담았으면 이를 이용해서 문제에서 원하는 격자판을 만들면 된다.
7. 격자판의 가로는 교점의 최소 x좌표 ~ 최대 x좌표이고 세로는 최소 y좌표 ~ 최대 y좌표이므로
   격자판의 가로 길이는 최대 x좌표 - 최소 x좌표 + 1이 되고 세로 길이는 최대 y좌표 - 최소 x좌표 + 1이 된다.
8. answer 배열에 격자판을 "."으로 채우기 위해서 answer 배열을 격자판의 세로 길이 크기로 생성한다.
9. StringBuilder를 생성하여 격자판의 가로 길이만큼 "."을 append() 해주고 격자판의 세로 길이인 answer에 전부 채워준다.
10. 이제 이 격자판에서 교점의 좌표에 해당하는 자리에 "."을 "*"로 변환해주면 된다.
11. 이렇게 격자판을 구하여 직사각형을 보면 맨 왼쪽 위의 좌표가 (0, 0)이 되는데 이 (0, 0)을 기준으로 교점의 좌표들을 조정해주어야 한다. (0, 0)인 맨 왼쪽 위 자리는 (최소 x, 최대 y)에 해당하는 자리인 것을 생각해서 조정하면 된다.
12. set에 넣은 교점들을 꺼내서 새롭게 조정한 교점의 x좌표는 (기존 교점 x좌표 - 최소 x)로 변환해주고 y좌표는 (최대 y - 기존 교점 y좌표)가 된다.
13. 이렇게 다시 조정하여 구한 x, y 좌표에 해당하는 자리의 "."을 "*"로 변환해주면 되는데 answer는 격자판의 세로 길이 크기이므로 answer[y좌표]에 해당하는 String 원소의 x인덱스 자리를 "*"로 변환한다. answer[y좌표]의 x좌표 전까지 substring()으로 자르고 해당 x좌표 자리에 "*"를 더해주고 다시 해당 x좌표 다음부터 마지막까지 substring()으로 자르고 전부 합쳐서 다시 저장하도록 한다.