이 글에서는 코틀린을 이용한 알고리즘 문제 해결을 위해 투 포인터 기법을 설명합니다. 투 포인터는 한 배열이나 리스트에서 두 개의 포인터를 이용하여 특정 조건을 만족하는 값이나 범위를 찾는 알고리즘 기법으로, 주로 정렬되어 있는 배열과 관련된 문제에서 많이 사용됩니다.
문제 설명
다음은 투 포인터를 사용하여 해결할 수 있는 문제입니다.
문제: 두 수의 합
주어진 정수 배열 nums와 정수 target가 있을 때, 두 수의 합이 target이 되는 두 수의 인덱스를 리턴하시오. 각 입력에 대해 정확히 하나의 정답이 존재한다고 가정합니다. 같은 요소를 두 번 사용할 수는 없습니다.
예를 들어:
- 입력:
nums = [2, 7, 11, 15], target = 9 - 출력:
[0, 1](nums[0] + nums[1] = 2 + 7 = 9)
문제 접근 방법
이 문제는 투 포인터 기법을 사용하여 해결할 수 있습니다. 하지만 먼저 배열을 정렬해야 하므로, 원래의 인덱스를 추적하는 것이 필요합니다. 일반적인 투 포인터 접근 방식으로 문제를 해결할 수 있습니다.
1단계: 입력 배열 정렬
배열을 정렬하여 각 포인터가 적절한 위치에서 비교할 수 있도록 합니다. 이 경우, 각 요소와 그 인덱스를 함께 저장할 필요가 있습니다.
2단계: 투 포인터 설정
한 포인터는 배열의 시작에서 시작하고, 다른 포인터는 배열의 끝에서 시작합니다. 두 포인터가 가리키는 값의 합이 target과 같거나 작은 경우 포인터를 이동시킵니다.
3단계: 조건 확인
합이 target보다 크면 오른쪽 포인터를 왼쪽으로 이동시키고, 작으면 왼쪽 포인터를 오른쪽으로 이동시킵니다. 두 포인터가 만날 때까지 이 과정을 반복합니다.
코틀린 코드
아래는 코틀린으로 구현한 코드입니다:
fun twoSum(nums: IntArray, target: Int): IntArray {
val indexedNums = nums.mapIndexed { index, num -> index to num }.sortedBy { it.second }
var left = 0
var right = indexedNums.size - 1
while (left < right) {
val sum = indexedNums[left].second + indexedNums[right].second
when {
sum == target -> return intArrayOf(indexedNums[left].first, indexedNums[right].first)
sum < target -> left++
else -> right--
}
}
throw IllegalArgumentException("No two sum solution")
}
시간 복잡도
이 알고리즘의 시간 복잡도는 O(n log n)입니다. 배열을 정렬하는 데 소요되는 시간이 가장 크기 때문입니다. 그 후 투 포인터 방식으로 변형된 두 수의 합을 찾는데 걸리는 시간은 O(n)입니다.
결론
투 포인터 기술은 매우 유용한 알고리즘 기법으로, 많은 문제들을 효율적으로 해결할 수 있습니다. 이 문제를 통해 투 포인터를 사용하여 배열을 관리하고 값을 찾아내는 방법을 배웠습니다. 연습을 통해 이 기법을 익히고 더 복잡한 문제를 해결할 수 있는 능력을 기르시기 바랍니다.
추가 연습 문제
다음은 추가로 연습할 수 있는 투 포인터 문제들입니다:
- 주어진 정수 배열에서 합이 특정 값인 모든 쌍을 찾는 문제
- 정렬된 배열에서 두 포인터를 사용하여 합이
k인 두 수의 쌍의 개수를 찾는 문제 - 문자열에서 두 포인터를 사용해 회문 여부를 확인하는 문제
위 문제들을 연습하면서 투 포인터 기법에 대한 이해를 더욱 깊이 있게 할 수 있습니다.