[Algorithm] Kotlin - programmers lv0 [ 겹치는 선분의 길이 ] - 테스트 1, 9번 오류 해결

[ Algorithm Link ]

프로그래머스

---

 

최종 코드 미리보기

 

private fun solution (arr : Array<IntArray>):Int{
    val table = IntArray(200)

    arr.forEach { for (i in it[0]+100 until it.last()+100){
        table[i]++
    } }

    return table.count{ it >= 2}
}

fun main() {
    val testA = intArrayOf(0, 8)
    val testB = intArrayOf(0, 2)
    val testC = intArrayOf(6, 8)
    val lines = arrayOf(testA, testB, testC)

    println(solution(lines))
}

 

 

[ 작성 코드 ]

 

table은 겹치는 선을 나타내는 범위로, 제한사항의 선의 좌표가 -100 .. 100 으로 겹칠 수 있는 넓이 200이 있다. 해당 배열 안에 선의 좌표 -100 ~ 100, 컬렉션의 인덱스는 - 값으로 위치를 찾을 수 없기 때문에 좌표에 +100을 해주고, 각 좌표값이 테이블 범위 안의 테이블[인덱스]에 해당하는 위치에 선이 포함될 시 해당 인덱스를 +1 해준다. IntArray(num) IntArray의 매개변수로 사이즈를 인자로 넣었을 때, 별도로 각 인덱스의 기본값을 지정하지 않을 경우 0으로 지정되기 때문에 위와 같이 표현 하는것이 가능하다.

 

결론 - 테이블 인덱스에 해당하는 범위에 선( 값) 이 있을 경우 +1, 즉 테이블의 특정 인덱스 값이 2 이상일 경우 2가지 선 이상이 겹치는 상황이 된다. 값이 2이상인 테이블의 인덱스 갯수를 찾아내면 겹치는 선분의 알 수 있다.

 

 

 

 

첫번째 제출 코드 - 테스트 1, 9 번 실패

 

[ 작성 코드 ]

class Solution {
    fun solution(lines: Array<IntArray>): Int {
    var testARange = lines[0][0]..lines[0][1]
    var testBRange = lines[1][0] .. lines[1][1]
    var testCRange = lines[2][0] .. lines[2][1]
    var lineA = testARange.filter { testBRange.contains(it) || testCRange.contains(it) }
    var lineB = testBRange.filter { testCRange.contains(it) }
    var answer = 0
    if (lineA.isNotEmpty() || lineB.isNotEmpty()) {
        var aLength = if (lineA.isNotEmpty()) {Math.abs(lineA.last() - lineA.first())} else { 0}
        var bLength = if (lineB.isNotEmpty()) {Math.abs(lineB.last() - lineB.first())} else { 0}
        var overlapLine = lineA.filter { lineB.contains(it) }
        var overlapLength = if (overlapLine.isNotEmpty()) {Math.abs(overlapLine.last() - overlapLine.first())} else { 0 }
        
        answer = aLength + bLength - overlapLength
    } 

    return answer
}
}

 

현상 : 코드 실행의 테스트 2개는 정상 실행되지만, 코드 제출 시 1번 9번 테스트에서 실패됨.

 

원인:

• 문제1. 입출력 [[0, 1], [1, 3], [-2, 0]] 기댓값 0 의 예시와 같이 선은 겹치지 않으나 좌표 일부가 겹치는 상황에서 문제가 발생.
• 문제2. 입출력 [[0, 2], [-3, -1], [-2, 1]] 기댓값 2의 예시 - 넓이 1의 선이 겹칠 때 문제 발생.
• 문제3. A Range가 겹치는 선의 넓이가 0이고, B Range가 C Range와 겹치는 선이 생길 때의 처리가 없다. 

 

 

 

 

제출 코드 - 통과 → 리팩토링 전

 

class Colution () {
    fun solution(lines: Array<IntArray>): Int {
        var lineARange = lines[0][0]..lines[0][1]
        var lineBRange = lines[1][0]..lines[1][1]
        var lineCRange = lines[2][0]..lines[2][1]

        var answer = 0
        if (lineARange.filter { lineBRange.contains(it) }.size >= 2
            && lineARange.filter { lineCRange.contains(it) }.size >= 2
            && lineBRange.filter { lineCRange.contains(it) }. size >= 2
        ) {
            var lineA = lineARange.filter { lineBRange.contains(it) || lineCRange.contains(it) }
            println("lineA = $lineA")
            var lineB = lineBRange.filter { lineCRange.contains(it) }
            println("lineB = $lineB")

            if (lineA.isNotEmpty() || lineB.isNotEmpty()) {
                val aLength = if (lineA.isNotEmpty()) {
                    Math.abs(lineA.last() - lineA.first())
                } else {
                    0
                }

                val bLength = if (lineB.isNotEmpty()) {
                    Math.abs(lineB.last() - lineB.first())
                } else {
                    0
                }
                val overlapLine = lineA.filter { lineB.contains(it) }
                val overlapLength = if (overlapLine.isNotEmpty()) {
                    Math.abs(overlapLine.last() - overlapLine.first())
                } else {
                    0
                }

                answer = aLength + bLength - overlapLength
                println("aLength = $aLength , bLength = $bLength overlapLeng = $overlapLength")
            }
            println("AB,BC,AC")
            return answer
        } else if (lineARange.filter { lineBRange.contains(it) }.size >= 2
            && lineARange.filter { lineCRange.contains(it) }.size < 2
            && lineBRange.filter { lineCRange.contains(it) }.size <2
        ) {
            var lineAB = lineARange.filter { lineBRange.contains(it) }
            val Length = if (lineAB.isNotEmpty()) {
                Math.abs(lineAB.last() - lineAB.first())
            } else {
                0
            }

            println("AB")
            answer = Length
            return answer
        } else if (lineARange.filter { lineBRange.contains(it) }.size >= 2
            && lineARange.filter { lineCRange.contains(it) }.size >= 2
            && lineBRange.filter { lineCRange.contains(it) }.size < 2){

            var lengthAB = lineARange.filter { lineBRange.contains(it) }
            var lengthAC = lineARange.filter { lineCRange.contains(it) }

            println("AB,AC")
            answer = Math.abs(lengthAB.last() - lengthAB.first()) + Math.abs(lengthAC.last() - lengthAC.first())
            return answer
        }
        else if (lineARange.filter { lineBRange.contains(it) }.size < 2
            && lineARange.filter { lineCRange.contains(it) }.size >= 2
            && lineBRange.filter { lineCRange.contains(it) }.size < 2
            ) {
            var lineAC = lineARange.filter { lineCRange.contains(it) }
            val Length = if (lineAC.isNotEmpty()) {
                Math.abs(lineAC.last() - lineAC.first())
            } else {
                0
            }

            println("AC")
            answer = Length
            return answer
        } else if (lineARange.filter { lineBRange.contains(it) }.size >= 2
            && lineARange.filter { lineCRange.contains(it) }.size < 2
            && lineBRange.filter { lineCRange.contains(it) }.size >= 2){

            var lengthAB = lineARange.filter { lineBRange.contains(it) }
            var lengthBC = lineBRange.filter { lineCRange.contains(it) }

            println("AB,BC")
            answer = Math.abs(lengthAB.last() - lengthAB.first()) + Math.abs(lengthBC.last() - lengthBC.first())
            return answer
        } else if (lineARange.filter { lineBRange.contains(it) }.size < 2
            && lineARange.filter { lineCRange.contains(it) }.size >= 2
            && lineBRange.filter { lineCRange.contains(it) }.size >= 2) {

            var lengthAC = lineARange.filter { lineCRange.contains(it) }
            var lengthBC = lineBRange.filter { lineCRange.contains(it) }


            println("AC,BC")

            answer = Math.abs(lengthAC.last() - lengthAC.first()) + Math.abs(lengthBC.last() - lengthBC.first())
            return answer

        }

        else {
            var lineBC = lineBRange.filter { lineCRange.contains(it) }
            val bLength = if (lineBC.isNotEmpty()) {
                Math.abs(lineBC.last() - lineBC.first())
            } else {
                0
            }

            println("BC")
            answer = bLength
            return answer
        }
    }
}

 

[ 작성 코드 정리 ]

• lineA, B, C 로 나누어 각각의 선이 겹치는 라인을 2 선으로 나누고 두개의 길이를 더하고, 겹치는 구간이 있다면 겹치는 구간의 길이를 겹치는 두 선의 합의 길이에서 빼는 간단한 방법으로 만들어 보려고 했다.
• 하지만 선 2개가 겹치는 경우 ( ac ab abc abac ... )를 일일이 노가다로 작성하는 코드로 만들어 버렸다. 만약 선의 갯수가 추가로 늘어나면 사용이 거의 불가능하다.
• 테스트 통과를 우선 목표로 작동되는 것에만 신경쓰다 보니 반복되는 코드도 많아 지저분해졌다.

 

 

 

알고리즘 회고

 

이번 알고리즘 문제를 처음 풀 때 제한사항과 작동 목표를 기준으로 구조를 잡는 것이 아니라 일단 예제 1,2 개를 작동되게 만드는 식으로 구조를 잡다 보니까 유지보수 없이 통과는 불가능 함과 더불어 유지보수가 매우 어려웠다. 

 

확장성 등 여러가지 측면에서 효율적이지 않은 코드를 작성하는 문제.

 

알고리즘을 많이 풀어보지도 않고 처음부터 괜찮은 구조를 만드는 것은 욕심이겠지만 작동 코드 구조를 잘 잡을 수 있도록 노력해봐야겠다.

 

 

 

 

 

 

 

 

---

[Reference]

 

리팩토링 참조 - programmers [ Sinoso 님 ]