[알고리즘 / Kotlin] 프로그래머스 - (10주차)교점에 별 만들기

교점에 별 만들기

문제 설명

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

 

입출력 예

 

참고 사항

Ax + By + E = 0 Cx + Dy + F = 0 두 직선의 교점이 유일하게 존재할 경우, 그 교점은 다음과 같습니다.

 

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

 

내 풀이

해당 문제는 여러 개의 직선이 주어지고 교점들이 이루는 최소의 사각형을 문자열로 표현하는 문제입니다. (주의할 점, 여기서 주어지는 교점은 정수여야 합니다.)

 

그래서 저는 다음과 같은 흐름으로 문제를 해결하였습니다.

1. 직선의 교점의 리스트들을 구한다.
2. 교점의 x, y의 최대값과 최솟값을 구한다.
3. 교점의 최소 사각형을 구해서 2차원 배열로 구현한다.
4. 사각형에서 교점에 해당하는 부분을 "*"로 표시한다.

 

fun getMeetDot(a: IntArray, b : IntArray) : IntArray?{
  
	val C : Long = a[0].toLong()*b[1].toLong() - a[1].toLong()*b[0].toLong() // AD-BC
	val A : Long = a[1].toLong() * b[2].toLong() - a[2].toLong() * b[1].toLong() //BF- ED
	val B : Long= b[0].toLong() * a[2].toLong() - a[0].toLong() * b[2].toLong() // EC- AF

	if(C.toInt() ==0)
    	return null
	else{
    if((A%C).toInt() !=0 || (B%C).toInt() !=0)
        return null

    return intArrayOf((A/C).toInt(), (B/C).toInt())
	}
}

해당 함수는 교점을 구해서 IntArray를 반환해주는 것입니다. 그리고 AD-BC = 0 인 경우와 교점이 정수가 아닌 경우를 제외해주어야 합니다.

주의할 것은 만약 AD-BC int 형으로 처리한다면 오버플로우가 나서 29번째 테스트 케이스에서 런타임 에러가 날 것입니다. (Int 범위 : –2,147,483,648 ~ 2,147,483,647)

 

meetDotList.forEach {
    xList.add(it[0])
    yList.add(it[1])
}

xList.sort()
yList.sort()

xlength = xList[xList.size-1] - xList[0] +1
ylength = yList[yList.size-1] - yList[0] +1

var matrix = Array(ylength, { Array(xlength, {"."}) })

각 x, y의 min과 max를 구해서 matrix라는 최소 사각형을 만들어 줍니다.

   meetDotList.forEach {
        matrix[yList[yList.size-1] - it[1]][it[0] - xList[0]] ="*"
    }

matrix에서 x, y 좌표는 matrix에서는 matrix [y좌표][x좌표]로 표시되고 (0,0)부터 시작하기 때문에 1 사분면을 뒤집은 형태가 나오므로 y좌표 = maxY- y , x좌표 = x - minX로 구할 수 있습니다.

 

부연 설명하면 기존의 교점에서 x축으로 대칭 이동을 하고 y의 최댓값만큼 위로 이동하고 x의 최솟값만큼 오른쪽으로 이동하면 됩니다.

 

📝 코드

class Solution {
    fun solution(line: Array<IntArray>): Array<String> {

        val answer : ArrayList<String> = ArrayList()
        val meetDotList : ArrayList<IntArray> = ArrayList()

        val xList : ArrayList<Int> = ArrayList()
        val yList : ArrayList<Int> = ArrayList()

        var xlength = 0
        var ylength = 0

      //교점 리스트 구하기
        for(i in line.indices){
        for(j in i+1 until line.size){
            if(getMeetDot(line[i],line[j]) != null) {
                getMeetDot(line[i], line[j])?.let { meetDotList.add(it) }
            }
        }
    }


    meetDotList.forEach {
        xList.add(it[0])
        yList.add(it[1])
    }

    xList.sort()
    yList.sort()

    xlength = xList[xList.size-1] - xList[0] +1
    ylength = yList[yList.size-1] - yList[0] +1

    var matrix = Array(ylength, { Array(xlength, {"."}) })

    meetDotList.forEach {
        matrix[yList[yList.size-1] - it[1]][it[0] - xList[0]] ="*"
    }

    var stringOfLine = ""
    for(i in 0 until ylength ){
        for(j in 0 until xlength){
            stringOfLine += matrix[i][j]
        }
        answer.add(stringOfLine)
        stringOfLine =""
    }


        return answer.toTypedArray()
    }

 fun getMeetDot(a: IntArray, b : IntArray) : IntArray?{

    val C : Long = a[0].toLong()*b[1].toLong() - a[1].toLong()*b[0].toLong() // AD-BC
    val A : Long = a[1].toLong() * b[2].toLong() - a[2].toLong() * b[1].toLong() //BF- ED
    val B : Long= b[0].toLong() * a[2].toLong() - a[0].toLong() * b[2].toLong() // EC- AF

    if(C.toInt() ==0)
        return null
    else{

        if((A%C).toInt() !=0 || (B%C).toInt() !=0)
            return null

        return intArrayOf((A/C).toInt(), (B/C).toInt())
    }
}

}

 

다른 사람의 풀이

예제 1

class Solution {
    fun solution(line: Array<IntArray>): Array<String> {
        val intersectionPoints = initSet(line)
        val (minX, minY, maxX, maxY) = getMinMax(intersectionPoints)
        val array = Array((maxY + 1 - minY)) { Array((maxX + 1 - minX)) { "." } }

        for ((x, y) in intersectionPoints) {
            array[(maxY - y).toInt()][(x - minX).toInt()] = "*"
        }
        return array.map { it.joinToString("") }.toTypedArray()
    }

    private fun getMinMax(intersectionPoints: Set<Pair<Long, Long>>): Array<Int> {
        val result = arrayOf(Int.MAX_VALUE, Int.MAX_VALUE, Int.MIN_VALUE, Int.MIN_VALUE)

        for ((x, y) in intersectionPoints) {
            result[0] = min(result[0], x.toInt())
            result[1] = min(result[1], y.toInt())
            result[2] = max(result[2], x.toInt())
            result[3] = max(result[3], y.toInt())
        }
        return result
    }

    private fun initSet(line: Array<IntArray>): Set<Pair<Long, Long>> {
        val mutableSet = mutableSetOf<Pair<Long, Long>>()

        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 div = a * d - b * c
                val topX = b * f - e * d
                val topY = e * c - a * f

                if (div == 0L) {
                    continue
                } else {
                    val x = topX / div
                    val y = topY / div

                    if (topX % div != 0L || topY % div != 0L)
                        continue
                    mutableSet.add(x to y)
                }
            }
        }
        return mutableSet
    }
}

 

 

배운 점

실제로 기존의 특정 알고리즘을 사용해서 해결하는 문제가 아닌 문제에 주어진 조건들을 이해하고 이를 구현하는 문제를 풀어보니 생각보다 어렵다는 느낌이 많이 들었습니다. 실제로 이러한 문제가 코딩 테스트에서 많은 시간을 잡아먹을 것 같다는 생각이 들었습니다.

 

깔끔하게 코드를 작성하려고 했는데 쉽게 되지 않아서 조금은 속상했습니다. 조금 더 제가 노력을 해야 되는 부분인 것 같습니다. 손으로 풀면 쉬운 수학 문제인데 이를 코드로 풀어내는 것은 별개의 문제라는 것을 다시 한번 느끼게 되었습니다.