1. 문제 설명
퇴사 준비를 하며, 스위프트 언어를 사용하여 알고리즘 문제를 해결하는 능력을 기르는 것이 중요합니다. 다음은 스위프트 코딩 테스트에서 자주 출제되는 문제 중 하나입니다.
문제: 배열의 두 수의 합
주어진 정수 배열 nums와 정수 target이 있을 때, nums에서 두 수의 합이 target과 같은 두 개의 인덱스를 반환하는 함수를 작성하세요. 각각의 입력에 대해 정확히 하나의 정답만 존재한다고 가정하며, 같은 요소를 두 번 사용할 수는 없습니다. 반환된 인덱스의 순서는 상관없습니다.
예시
입력: nums = [2, 7, 11, 15], target = 9
출력: [0, 1] // nums[0] + nums[1] == 9
2. 문제 이해 및 접근법
이 문제는 다음과 같이 접근할 수 있습니다:
- 이중 루프를 사용하여 모든 가능한 두 수 조합을 검사하는 방법
- 해시 맵을 사용하여 한 번만 순회하면서 필요 조건을 확인하는 방법
조건을 최적으로 충족하기 위해 해시 맵을 사용하는 방식을 선택하겠습니다. 이 구현은 타임 복잡도가 O(n)이며, 공간 복잡도는 O(n)입니다.
3. 스위프트 구현
3.1. 필요 라이브러리 및 기본 구조 설정
import Foundation
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numDict = [Int: Int]()
// 함수 내용이 여기에 들어갈 예정입니다.
}
3.2. 해시 맵을 이용한 구현
다음 코드는 해시 맵을 사용하여 두 수의 인덱스를 찾는 기능을 구현합니다:
import Foundation
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numDict = [Int: Int]()
for (index, num) in nums.enumerated() {
let complement = target - num
if let complementIndex = numDict[complement] {
return [complementIndex, index]
}
numDict[num] = index
}
return []
}
4. 함수 설명
위의 twoSum 함수는 다음과 같은 작업을 수행합니다:
- 주어진 배열
nums를 순회하면서 각 정수를 해시 맵에 저장합니다. - 각 정수에 대해
target에서 그 수를 뺀 값을 계산합니다. 이를complement라고 부릅니다. - 해시 맵에서
complement가 존재하는지 확인합니다. 존재한다면 그 인덱스를 결과 배열에 추가합니다. - 만약 존재하지 않는다면 현재 숫자와 그 인덱스를 해시 맵에 추가합니다.
5. 테스트 케이스
구현된 함수를 테스트하기 위해 여러 케이스를 작성해보겠습니다.
let nums1 = [2, 7, 11, 15]
let target1 = 9
print(twoSum(nums1, target1)) // [0, 1]
let nums2 = [3, 2, 4]
let target2 = 6
print(twoSum(nums2, target2)) // [1, 2]
let nums3 = [3, 3]
let target3 = 6
print(twoSum(nums3, target3)) // [0, 1]
6. 복잡도 분석
twoSum 함수의 시간 복잡도는 O(n)입니다. 이는 배열을 한 번 순회하기 때문입니다. 공간 복잡도는 O(n)으로, 해시 맵에 최대 n개의 요소를 저장할 수 있기 때문입니다.
7. 마무리 및 추가 학습
스위프트를 사용한 코딩 테스트 준비에 있어 배열의 두 수의 합 문제는 매우 중요한 문제입니다. 이 문제를 통해 해시 맵의 효율성을 이해하고 활용할 수 있습니다. 앞으로 다양한 알고리즘 문제를 풀며 실력을 키우는 데 집중해봅시다.