프로그래머스 삼총사 다르게 풀어보기 with Kotlin

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

프로그래머스

 

 

이 문제는 3중 For문을 이용해 Brute Force 방식으로 풀 수 있으며, 검색해보면 나오는 대다수의 코드는 그렇게 풀고 있다.

다른 방법은 없을까?

 

Cursor 이용하기

아이디어의 시작은 이러했다.

1. number를 정렬한다.

2. 왼쪽에는 가장 작은 값, 오른쪽에는 가장 큰 값이 오므로, cursor를 이용해서 탐색할 수 있겠구나!

 

class Solution {
    fun solution(number: IntArray): Int {
        var answer: Int = 0

        number.sort()

        if (number.first() > 0 || number.last() < 0) {
            return 0
        }

        for (i in number.indices) {
            if (number[i] > 0) break

            var left = i+1
            var right = number.lastIndex

            while (left < right) {
                val sum = number[i] + number[left] + number[right]

                when {
                    sum == 0 -> {
                        val beforeLeftIndex = left
                        val beforeLeftValue = number[left]
                        val beforeRightValue = number[right]

                        // handle case which left is same with right like -4, 2, 2, 2, 2
                        if (beforeLeftValue == beforeRightValue) {
                            answer += (right - left + 1) * (right - left) / 2
                            break
                        }

                        var sameCountOfLeft = 1
                        left++
                        while (left < right && number[left] == beforeLeftValue) {
                            sameCountOfLeft++
                            left++
                        }

                        var sameCountOfRight = 1
                        right--
                        while (beforeLeftIndex <= right && number[right] == beforeRightValue) {
                            sameCountOfRight++
                            right--
                        }
                        answer += sameCountOfLeft * sameCountOfRight
                    }
                    sum > 0 -> right--
                    else -> left++
                }
            }
        }
        return answer
    }
}

 

 

 

 

하지만 이 코드는 3중 for문 보다 느리다(평균 0.02ms가 걸림). number의 최대 길이 값이 13으로 매우 작기 때문에 number를 정렬하는 것과, cursor의 조작이 오히려 소요 시간을 늘리는 것 같다.

 

배운 점

left, right cursor를 이용할 때, 탐색하지 못하는 edge case가 발생하는 것을 유의해야 한다.

예를 들어, [-5, -3, -3, 8, 8]이 있다고 하자. cursor를 이용해 answer를 1개씩 카운트할 경우, [0, 1, 3] 케이스에 도달할 수 없다.

이것을 보여주는 코드는 아래와 같다.

class Solution {
    fun solution(number: IntArray): Int {
        var answer: Int = 0

        number.sort()

        if (number.first() > 0 || number.last() < 0) {
            return 0
        }

        for (i in number.indices) {
            if (number[i] > 0) break

            var left = i+1
            var right = number.lastIndex

            while (left < right) {
                val sum = number[i] + number[left] + number[right]

                when {
                    sum == 0 -> {
                        answer++
                        val beforeLeftValue = number[left]
                        val beforeRightValue = number[right]
                        left++
                        while (left < right && number[left] == beforeLeftValue) {
                            answer++
                            left++
                        }
                        right--
                        while (left < right && number[right] == beforeRightValue) {
                            answer++
                            right--
                        }
                    }
                    sum > 0 -> right--
                    else -> left++
                }
            }
        }
        return answer
    }
}

 

그래서, right의 같은 값을 탐색할 때, `left < right`가 아닌 `beforeLeftIndex <= right` 조건문을 이용했다. 원래 코드에서 left와 right의 값이 동일한 경우를 사전에 처리해줬기 때문에 beforeLeftIndex == right인 경우는 발생하지 않는다.

 

하지만 이것 만으로도 모든 case에 대응이 되지 않았다. 그래서 sum이 0일 때, left와 right의 연속한 동일한 값의 갯수를 센 후, 조합(left 갯수 * right 갯수)의 합을 answer에 더해줬다.

또한, 이 코드 만으로는 left와 right 값이 같은 경우에도 도달할 수 없는 edge case가 존재한다.( -4, 2, 2, 2, 2 )

그래서 왼쪽값과 오른쪽값이 동일한 경우를 사전에 if문으로 확인한 후 별도로 처리해준 것이다.

 

발견한 테스트 케이스 값

테스트 1 케이스로 추정되는 경우 : -4, 2, 2, 2, 2

테스트 6 케이스로 추정되는 경우 : -5, -3, -3, -3, 8, 8, 8, 8