코딩 테스트를 준비하는 여러분을 위해, 스위프트 언어로 풀 수 있는 알고리즘 문제를 소개합니다. 이번 문제는 ‘원하는 정수 찾기’로, 주어진 정수 배열 내에서 특정 정수를 찾는 알고리즘을 구현하게 됩니다. 이 글에서는 문제 설명부터 알고리즘 솔루션까지의 과정을 자세히 설명하겠습니다.
문제 설명
주어진 정수 배열 numbers가 있습니다. 이 배열에서 특정 정수 target이 존재하는지 확인하는 함수를 작성하세요. 만약 존재한다면 해당 정수의 인덱스를 반환하고, 존재하지 않으면 -1을 반환하세요.
func findTarget(numbers: [Int], target: Int) -> Int입력
numbers: 정수로 이루어진 배열 (1 ≤ numbers의 길이 ≤ 106)target: 찾고자 하는 정수 (-109 ≤ target ≤ 109)
출력
target이 존재하는 경우 해당하는 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다.
예제
예제 1
입력: numbers = [1, 2, 3, 4, 5], target = 3
출력: 2예제 2
입력: numbers = [5, 6, 7, 8, 9], target = 1
출력: -1솔루션 접근 방법
이 문제를 해결하기 위해서는 배열 내에서 target이 위치한 인덱스를 찾는 방법을 생각해야 합니다. 기본적인 방법으로는 반복문을 통한 선형 탐색이 있으며, 배열이 정렬된 경우 이분 탐색을 사용할 수 있습니다.
1. 선형 탐색
선형 탐색은 배열의 처음부터 끝까지 하나씩 확인하면서 target을 찾는 방식입니다. 배열의 길이에 따라 시간 복잡도는 O(n)입니다.
2. 이분 탐색
배열이 정렬된 경우 이분 탐색이 훨씬 효율적입니다. 이 방법은 배열의 중간 인덱스를 기반으로 검색 범위를 절반으로 줄여가며 target을 찾습니다. 이 경우의 시간 복잡도는 O(log n)입니다.
구현
우리는 우선 선형 탐색을 구현한 후, 이분 탐색에 대해서도 구현해보겠습니다.
선형 탐색 구현
func findTarget(numbers: [Int], target: Int) -> Int {
for (index, number) in numbers.enumerated() {
if number == target {
return index
}
}
return -1
}이분 탐색 구현
func binarySearch(numbers: [Int], target: Int) -> Int {
var left = 0
var right = numbers.count - 1
while left <= right {
let mid = (left + right) / 2
if numbers[mid] == target {
return mid
} else if numbers[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}테스트 케이스
우리가 작성한 함수를 테스트하기 위해 몇 가지 케이스를 실행해보겠습니다.
let numbers = [1, 2, 3, 4, 5]
let target1 = 3
let target2 = 6
print(findTarget(numbers: numbers, target: target1)) // 2
print(findTarget(numbers: numbers, target: target2)) // -1성능 평가
선형 탐색은 간단하지만, 최악의 경우 모든 요소를 탐색해야 하므로 평균적으로 O(n)의 시간이 소요됩니다. 반면, 이분 탐색은 정렬된 배열에서 더 나은 성능을 발휘하며 O(log n)을 보장합니다. 그러므로 대규모 데이터셋의 경우 이분 탐색을 권장합니다.
결론
이번 문제를 통해 우리는 스위프트에서 정수를 배열에서 찾는 방법에 대해 배웠습니다. 기본적인 선형 탐색을 통해 문제를 해결하는 방법을 이해하였고, 더 효율적인 이분 탐색으로 성능을 개선할 수 있는 방법도 알아보았습니다. 지속적인 연습을 통해 알고리즘 문제 풀이에 대한 감각을 키우시길 바랍니다.