코틀린 코딩테스트 강좌, ‘좋은 수’ 구하기

문제 설명

‘좋은 수’는 주어진 정수 리스트에서 서로 다른 수(A, B, C, …)를 선택하여 A + B + C = 0이 되는 경우를 찾는 문제입니다. 예를 들어, 다음과 같은 배열이 주어졌다고 가정합시다.

 [-1, 0, 1, 2, -1, -4] 

위 배열에서 합이 0이 되는 수의 조합은 (-1, 0, 1)과 (-1, -1, 2)입니다. 이러한 조합을 모두 찾아서 반환하여야 합니다.

문제 접근 방식

이 문제를 해결하기 위해서는 몇 가지 기본적인 접근 방식을 고려해야 합니다.

1. 정렬: 배열을 정렬함으로써 같은 수를 효과적으로 다룰 수 있고, 두 포인터 기법이나 이진 탐색 등의 알고리즘을 적용할 수 있습니다.
2. 중복 제거: 같은 숫자를 여러 번 더하지 않도록 처리해야 합니다.
3. 포인터 기법: 정렬된 리스트를 기반으로 두 개의 포인터를 사용하는 방법으로, 각 조합을 효율적으로 확인할 수 있습니다.

알고리즘 설계

알고리즘은 다음과 같은 단계로 이루어집니다.

1. 입력 배열을 정렬합니다.
2. 그 다음, 각 요소에 대해 두 개의 포인터를 사용하여 합이 0이 되는지 검사합니다.
3. 결과 리스트에 추가하는 과정에서 중복을 피하도록 합니다.

코드 구현

이제 코드를 구현해 보겠습니다. 코틀린으로 다음과 같이 작성합니다:

        fun threeSum(nums: IntArray): List> {
            nums.sort() // 배열 정렬
            val res = mutableListOf>()
            for (i in nums.indices) {
                if (i > 0 && nums[i] == nums[i - 1]) continue // 중복 체크
                var left = i + 1
                var right = nums.size - 1
                while (left < right) {
                    val sum = nums[i] + nums[left] + nums[right]
                    when {
                        sum < 0 -> left++      // 합이 작으면 왼쪽 포인터 이동
                        sum > 0 -> right--     // 합이 크면 오른쪽 포인터 이동
                        else -> {
                            res.add(listOf(nums[i], nums[left], nums[right])) // 합이 0인 경우 추가
                            while (left < right && nums[left] == nums[left + 1]) left++ // 중복 체크
                            while (left < right && nums[right] == nums[right - 1]) right-- // 중복 체크
                            left++
                            right--
                        }
                    }
                }
            }
            return res
        }
        

코드 분석

코드의 각 부분을 분석해 보겠습니다.

1. 배열 정렬:  `nums.sort()`를 통해 배열을 오름차순으로 정렬합니다. 이는 두 포인터 기법을 적용하기 위한 필수 단계입니다.
2. 메인 루프: 인덱스를 기준으로 반복하며 각 요소를 선택합니다. 중복이 있을 경우에는 넘어갑니다.
3. 두 포인터: 선택된 요소를 기반으로 왼쪽과 오른쪽 포인터를 설정합니다. 이들 포인터를 이동하며 세 개의 요소의 합을 계산하고 비교합니다.

최적화 및 시간 복잡도

이 알고리즘의 시간 복잡도는 O(n^2)입니다. 외부 루프가 n번 반복되고, 내부 while 루프가 최대 n번 반복되기 때문입니다. 이로 인해 리스트의 크기가 커질수록 시간 복잡도는 급격히 증가할 수 있으므로 효율적인 처리가 필요합니다.

공간 복잡도는 O(1)으로, 입력 외의 추가적인 공간을 사용하지 않습니다. 다만, 결과 리스트를 저장하는 데 필요한 공간이 사용됩니다.

예제 및 실행 결과

예제 입력과 결과를 통해 이해를 돕겠습니다.

        val input = intArrayOf(-1, 0, 1, 2, -1, -4)
        val result = threeSum(input)
        println(result) // Output: [[-1, -1, 2], [-1, 0, 1]]
        

결론

본 강좌에서는 코틀린을 사용하여 ‘좋은 수’를 구하는 알고리즘을 설계하고 구현하는 과정을 살펴보았습니다. 정렬, 중복 체크 및 두 포인터 기법을 활용함으로써 문제를 효율적으로 해결할 수 있었습니다. 이와 같은 문제를 풀며 알고리즘적 사고와 코딩 능력을 향상시키는 데에 도움이 되길 바랍니다.

앞으로도 다양한 알고리즘 문제를 통해 여러 해법을 탐구해보는 시간을 가져보세요!