코틀린 코딩테스트 강좌, 어떤 알고리즘으로 풀어야 할까

이번 글에서는 코틀린을 사용한 코딩 테스트에서 자주 출제되는 알고리즘 문제를 하나 소개하고, 이를 해결하는 과정을 자세히 다루어보겠습니다. 코딩 테스트는 다양한 문제 해결 능력을 요구하는 중요한 수단으로 자리 잡고 있으며, 특정 알고리즘을 잘 이해하고 활용하는 것이 성공적인 코딩 테스트의 핵심입니다.

문제 설명

다음은 코팅 테스트에서 출제될 수 있는 일반적인 문제입니다.

문제: 두 수의 합

정수 배열 numbers와 정수 target가 주어집니다. 이때, numbers에 있는 두 수를 더한 값이 target과 같도록 만드는 두 수의 인덱스를 찾아 반환하는 함수를 작성하시오. 만약 해당하는 두 수가 없다면 -1을 반환합니다.

입력 예시

numbers = [2, 7, 11, 15]
target = 9

출력 예시

[0, 1]

문제 해결 접근 방식

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.

1. 완전 탐색 (Brute Force)

가장 간단하면서도 직관적인 접근 방법은 두 개의 중첩 반복문을 사용하여 모든 가능한 두 수의 조합을 확인하는 것입니다. 그러나 이 방법은 시간 복잡도가 O(n^2)로 매우 비효율적입니다.

2. 해시맵을 이용한 접근

더 효율적인 방법은 해시맵(또는 딕셔너리)을 활용하는 것입니다. 이 방법은 시간 복잡도가 O(n)으로, 하나의 반복문만으로 문제를 해결할 수 있습니다.

각 수를 해시맵에 저장하면서, 현재 수와 더하여 target이 되는 수가 해시맵에 있는지를 확인합니다.
해시맵에는 각 수와 그 수의 인덱스를 저장합니다.

코틀린으로 구현하기

이제 앞서 설명한 해시맵을 이용한 접근 방법을 코틀린으로 구현해 보겠습니다.

fun twoSum(numbers: IntArray, target: Int): IntArray {
    val map = mutableMapOf()

    for (i in numbers.indices) {
        val complement = target - numbers[i]
        // complement가 map에 있는지 확인
        if (map.containsKey(complement)) {
            // 인덱스를 찾았으니 반환
            return intArrayOf(map[complement]!!, i)
        }
        // 현재 숫자와 인덱스를 저장
        map[numbers[i]] = i
    }
    // 해당하는 두 수가 없을 경우 -1 반환
    return intArrayOf(-1)
}

코드 설명

위 코드를 하나씩 살펴보겠습니다.

fun twoSum(numbers: IntArray, target: Int): IntArray: 함수의 파라미터로 정수 배열과 목표 정수를 받습니다.
val map = mutableMapOf(): 해시맵을 생성하여 각 숫자와 그 인덱스를 저장할 준비를 합니다.
for (i in numbers.indices): 주어진 배열을 순회하여 각 원소의 인덱스를 가져옵니다.
val complement = target - numbers[i]: 현재 숫자와 더하여 target이 되는 다른 숫자를 계산합니다.
if (map.containsKey(complement)): 해시맵에 ‘complement’가 존재하는지 확인합니다.
return intArrayOf(map[complement]!!, i): ‘complement’가 존재한다면, 두 수의 인덱스를 배열로 반환합니다.
마지막으로 현재 숫자와 그 인덱스를 해시맵에 추가하고, 반복을 계속합니다.

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n) 입니다. 이는 배열을 한 번 순회하면서 해시맵에 접근하는 데 상수 시간 복잡도를 가지기 때문입니다. 따라서, 입력 배열의 크기에 비례하여 수행 시간이 증가합니다. 공간 복잡도는 또한 O(n)인데, 이는 해시맵에 최악의 경우 모든 숫자가 저장될 수 있기 때문입니다.

정리

이번 포스트에서는 코틀린 알고리즘 문제를 하나 해결해 보았습니다. 해시맵을 활용하여 문제를 효율적으로 해결하는 방법을 살펴보았습니다. 이러한 문제들은 코딩 테스트에서 자주 출제되므로, 여러 문제를 풀어보면서 감각을 익히는 것이 중요합니다. 또한, 코틀린의 다양한 기능을 익히고 활용하는 것도 코딩 테스트 준비에 큰 도움이 될 것입니다.

마무리

다음 포스팅에서는 다른 알고리즘 주제를 다루어보도록 하겠습니다. 각종 알고리즘을 잘 알고 활용하는 것이 중요하니 꾸준한 연습을 통해 실력을 키워 나가길 바랍니다. 질문이나 의견이 있다면 댓글로 남겨주세요.