최근 많은 기업들이 채용 과정에서 코딩 테스트를 실시하고 있습니다. 이 글에서는 여러분이 스위프트 프로그래밍 언어를 사용하여 코딩 테스트를 준비하는 데 도움이 될 수 있는 문제를 하나 다루고, 해당 문제를 효율적으로 해결하는 방법에 대해 자세히 설명하겠습니다.
문제: 배열의 두 수의 합
주어진 정수 배열 nums와 정수 target이 있을 때, 배열에서 두 수의 합이 target과 같은 두 개의 인덱스를 찾는 문제를 해결해야 합니다. 각 입력은 정확히 하나의 해결책이 있다고 가정하며, 동일한 요소를 두 번 사용할 수는 없습니다.
입력 형식
nums: [2, 7, 11, 15]target: 9
출력 형식
[0, 1] (nums[0] + nums[1] = 2 + 7 = 9)
문제 분석
이 문제는 매우 유명한 문제로, 다양한 방법으로 해결할 수 있습니다. 가장 기본적인 접근 방법은 이중 루프를 사용하는 것이며, 이는 시간 복잡도가 O(n^2)입니다. 그러나 더 효율적인 방법을 찾아보겠습니다.
효율적인 접근법: 해시 맵 사용하기
주어진 배열을 순회하면서 각 요소를 해시 맵에 저장하는 방식을 사용할 수 있습니다. 해시 맵을 사용하면 검색 시간을 O(1)로 줄일 수 있어 전체 시간 복잡도를 O(n)으로 감소시킬 수 있습니다.
문제 풀이 단계
- 빈 해시 맵을 생성합니다.
- 배열을 순회하면서 현재 수
current와target - current의 차이를 계산합니다. - 해시 맵에
target - current가 존재하면, 해당 인덱스와 현재 인덱스를 반환합니다. - 현재 수와 인덱스를 해시 맵에 추가합니다.
스위프트 코드
let nums = [2, 7, 11, 15]
let target = 9
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
}
// 해결책이 없을 경우 nil 반환
return nil
}
if let result = twoSum(nums: nums, target: target) {
print(result) // [0, 1]
}
결과 확인
위 코드를 실행하면 [0, 1]라는 결과를 출력합니다. 이는 nums[0]과 nums[1]의 합이 target과 같음을 확인할 수 있습니다.
최적화 고려사항
이 알고리즘은 주어진 문제에 대해 최적화된 접근 방식을 보여줍니다. 해시 맵을 사용하는 방식을 통해 평균적으로 O(n)시간 복잡도로 문제를 해결할 수 있습니다. 그러나 최악의 경우 해시 충돌로 인해 성능이 저하될 수 있으니, 적절한 해시 함수를 사용하는 것이 중요합니다.
결론
이 글에서는 스위프트를 활용하여 코딩 테스트 문제를 해결하는 방법을 살펴보았습니다. 해시 맵을 이용한 접근법은 다양한 상황에서 활용될 수 있으며, 효율적인 코드를 작성하는 데 큰 도움을 줄 수 있습니다. 지속적으로 다양한 알고리즘 문제를 풀어보며 자신의 실력을 키워나가길 바랍니다.
앞으로도 다양한 알고리즘 문제와 그 해결책을 다루는 강좌가 계속될 예정이니, 많은 관심 부탁드립니다!