코틀린 코딩테스트 강좌, 원하는 정수 찾기

문제 설명

주어진 정수 배열에서 특정 정수를 찾는 프로그램을 작성하십시오. 함수는 다음과 같은 시그니처를 가집니다:

fun findNumber(arr: IntArray, target: Int): Boolean

입력으로 주어지는 arr는 정수 배열이며, target은 우리가 찾고자 하는 정수입니다.
만약 target이 배열에 존재하면 true를 반환하고, 그렇지 않으면 false를 반환해야 합니다.

예제

입력

arr = [1, 2, 3, 4, 5]
target = 3

출력

true

입력

arr = [1, 2, 3, 4, 5]
target = 6

출력

false

풀이 접근법

이 문제를 해결하기 위해서는 배열을 탐색하여 타겟 숫자가 존재하는지를 확인할 필요가 있습니다. 배열 탐색 알고리즘에는 여러 가지가 있지만, 여기서는 가장 기본적인 선형 검색을 사용하겠습니다.
배열의 각 요소를 순차적으로 검사하여 목표 숫자가 발견되면 true를 반환합니다.

만약 배열을 끝까지 검사하게 되면 false를 반환합니다. 이 방식은 시간 복잡도가 O(n)으로, 배열의 길이에 비례해서 실행 시간이 증가합니다.
그러나 배열이 정렬되어 있는 경우 이진 탐색 알고리즘을 사용할 수 있어, 시간 복잡도를 O(log n)으로 줄일 수 있습니다. 여기서는 단순화를 위해 선형 검색을 구현하겠습니다.

코드 구현

이제 코틀린을 사용하여 이 문제를 해결하는 코드를 작성해보겠습니다.

fun findNumber(arr: IntArray, target: Int): Boolean {
        for (number in arr) {
            if (number == target) {
                return true
            }
        }
        return false
    }

코드 설명

위의 코드는 배열 arr의 모든 요소에 대해 반복문을 실행합니다. 각 요소가 target과 같은지 비교하고, 같다면 true를 반환합니다.
반복문이 끝날 때까지 target이 발견되지 않으면 false를 반환합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 배열의 크기 n에 비례해서 탐색하는 시간이 증가하기 때문입니다.
공간 복잡도는 O(1)로 추가적인 메모리를 사용하지 않습니다. 이는 최적의 공간 복잡도를 가지고 있음을 의미합니다.

테스트 케이스

추가 테스트 케이스

val testArray = intArrayOf(10, 20, 30, 40, 50)
println(findNumber(testArray, 30)) // true
println(findNumber(testArray, 60)) // false
println(findNumber(intArrayOf(), 1)) // false
println(findNumber(intArrayOf(5), 5)) // true
println(findNumber(intArrayOf(5), 10)) // false

결론

이 예제를 통해 코틀린을 사용한 간단한 탐색 알고리즘을 작성하는 방법을 배웠습니다. 선형 검색은 가장 기본적인 통합 규칙으로,
실제 프로젝트에서는 데이터양과 복잡성에 따라 적절한 알고리즘을 선택하는 것이 중요합니다.
이를 통해 다양한 종류의 문제를 풀 수 있는 능력을 기를 수 있습니다.