프로그래머스 교점에 별 만들기 Kotlin (구현)

문제 출처 : https://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 크기 이내에서 표현됩니다.
• 별이 한 개 이상 그려지는 입력만 주어집니다.

입출력 예

입출력 예 설명

입출력 예 #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인 경우 두 직선은 평행 또는 일치합니다.

풀이

어우 프로그래머스에서 문제 긁어올 때 뭔가 문제가 많아졌다.

이제 대충 긁고 입출력 부분만 캡쳐본 사용해야지.

구현, 그래프, 수학 정도로 분류할 수 있는 문제이다.

문제에서 이런 교점을 구하는 공식을 제공해 줬는데 이를 보지 못하고 수학..... 하면서 생 구현하다가 공식을 발견하고 다시 풀었다.

우선 문제의 전체적인 풀이 과정은 다음과 같다.

1. 교점을 모두 찾는다

2. 그래프를 딱 맞는 사이즈로 그려야 하므로 찾은 교점들을 이용해 maxX, minX, maxY, minY 값을 구한다.

3. max,min  xy좌표를 이용해 그래프의 사이즈를 지정한다.

4. 교점들의 x,y좌표를 r,c로 변환하여 별을 그린다.

 

1. 교점을 모두 찾는다

우선 교점을 찾는 것은 위의 공식대로 구현하면 된다.

여기서 주의할 점은 A*B 혹은 B*C의 값들이 Int를 벗어날 수 있다는 점

따라서 우선 주어진 입력을 Long값으로 변환하여 계산을 마친 후 최종적으로 x,y는 다시 Int로 바꾸어 놓는다.

사실 그대로 x, y를 Long으로 해도 되긴 한데 본인은 Int가 편하다.

평행한 경우는 문제에 나와있으니 당연히 교점에서 제외하고,

x,y가 소수로 나오는 경우도 있다.

이 경우는 좌표상에 나타낼 수 없으니 이것도 교점에서 제외해야 한다.

찾은 교점들은 배열에 저장해 둔다.

 

2. 그래프를 딱 맞는 사이즈로 그려야 하므로 찾은 교점들을 이용해 maxX, minX, maxY, minY 값을 구한다.

1번 과정에서 교점을 찾으면서 최대, 최소 좌표값들을 갱신한다.

 

3. max,min  xy좌표를 이용해 그래프의 사이즈를 지정한다.

maxX, minX, maxY, minY를 이용해 별을 그릴 그래프의 사이즈를 지정하자.

어떻게?

본인은 x,y로 주어진 그래프를 행렬로 바꾸는 게 항상 헷갈리지만, 그래도 눈 부릅뜨고 그래프를 쳐다보면 할 수 있다.

눈을 부릅뜨고 보면 

그래프의 높이는 maxY-minY+1

너비는 maxX-minX+1

이란 것을 알 수 있다...!

귀찮아서 설명하지 않는 게 아니라 진짜 예제로 주어진 그래프를 보면 알 수 있다.

 

4. 교점들의 x,y좌표를 r,c로 변환하여 별을 그린다.

다시... 눈을 부릅뜨자

일단 r,c로 변환할 때 기준은 그래프의 좌측 최상단이 0,0으로 기준점이 된다.

여기서 직접 아래 사진의 교점 좌표값(x,y)를 0,0기준으로 바꾸어보면

r = maxY-y

c = x - minX

라는 식이 나온다.

이제 이 r,c를 이용해 3번 과정에서 만든 그래프에 별을 찍어주면 된다.

 

이 문제의 핵심이라 할 수 있는 3,4 번 과정에 대한 설명이 조금 불친절했다 느낄 수 있는데, 절대 귀찮아서가 아니다. 정말로.

이 문제를 '구현'이라 분류한 것은 특별한 알고리즘이 필요하지 않고 정말 주어진 예제를 두 눈 부릅뜨고 계산해 보면 식이 나온다.

음 사실 설명은 충분한데 내가 이런 것을 잘하지 못해서 뭔가 설명이 조금 부족했다고 느끼는 걸 수도 있다.

무튼 일부러 3,4번에 대한 설명을 저렇게 했으니 직접 계산해보길 바란다. 

코드

class Solution {
    
    val INF = Int.MAX_VALUE
    
    var maxY=-INF
    var maxX=-INF
    var minY=INF
    var minX=INF
    
    fun solution(line: Array<IntArray>): Array<String> {
        val xyArr = ArrayList<Pair<Int,Int>>()
        
        for(i in line.indices){
            for(j in i+1 until line.size){
                val (A,B,E) = line[i].map{it.toLong()}
                val (C,D,F) = line[j].map{it.toLong()}

                val adbc = A*D-B*C
                val bfed = B*F-E*D
                val ecaf = E*C-A*F
                //평행한 경우
                if(adbc == 0L) continue
                //정수가 아닌 경우
                if(bfed%adbc!=0L || ecaf%adbc!=0L) continue
                
                val x = (bfed/adbc).toInt()
                val y = (ecaf/adbc).toInt()

                //x,y저장
                xyArr.add(Pair(x,y))
                
                //최대 최소 갱신
                maxX = maxX.coerceAtLeast(x)
                minX = minX.coerceAtMost(x)
                maxY = maxY.coerceAtLeast(y)
                minY = minY.coerceAtMost(y)
                
            }
        }
    
        //별 찍기
        val graph = Array(maxY-minY+1){CharArray(maxX-minX+1){'.'}}
    
        for(xy in xyArr){
            val r = maxY-xy.second
            val c = xy.first-minX
            graph[r][c]='*'
        }
        
        val answer = Array(graph.size){String(graph[it])}

        return answer
    }
}