알고리즘 문제 해결에서 시간 복잡도를 이해하는 것은 매우 중요합니다. 시간 복잡도는 알고리즘의 효율성을 평가하는 데 핵심 요소로, 주어진 입력 크기에 따라 알고리즘이 얼마나 빠르게 실행되는지를 나타냅니다.
이번 강좌에서는 스위프트를 사용하여 알고리즘 문제를 해결하는 과정에서 시간 복잡도를 분석하고, 이를 통해 효율적인 코드를 작성하는 방법을 배우겠습니다.
문제: 두 배열에서 공통 요소 찾기
주어진 두 개의 정수 배열, A와 B가 있습니다. 두 배열에서 공통적으로 존재하는 모든 요소를 찾아 하나의 배열로 반환하는 함수를 작성하세요.
문제 설명
- 입력: 두 개의 정수 배열
A와B(0 ≤ A.length, B.length ≤ 1000) - 출력: 두 배열의 공통 요소를 포함하는 배열 (중복 요소는 제외)
예제
입력: A = [1, 2, 3, 4, 5], B = [3, 4, 5, 6, 7]
출력: [3, 4, 5]
풀이 과정
1. 문제 이해하기
주어진 두 배열에서 중복 요소를 제외하고 공통적인 요소를 찾는 문제입니다.
배열의 크기가 최대 1000이기 때문에, 최대 2,000개의 요소를 비교해야 할 수 있습니다.
따라서 O(n^2) 복잡도를 가진 단순한 중첩 반복문으로 해결할 수도 있지만, 더 효율적인 해결 방법을 모색해보겠습니다.
2. 효율적인 방법 탐색
공통 요소를 찾기 위해 두 배열을 비교하면서, 각 배열의 요소를 나열하고 중복을 피할 수 있는 방법을 고민해 봅시다.
해시셋(HashSet)을 활용하면 O(n) 시간복잡도로 해결할 수 있습니다.
우선 배열 A를 해시셋에 저장한 후, 배열 B를 순회하면서 해시셋에 존재하는 요소를 확인하면 됩니다.
3. 스위프트 코드 구현
func findCommonElements(A: [Int], B: [Int]) -> [Int] {
var setA = Set(A) // 배열 A의 요소를 해시셋에 저장
var result: [Int] = [] // 결과를 저장할 배열
for element in B { // 배열 B의 각 요소를 순회
if setA.contains(element) { // 해시셋에 존재하는지 확인
result.append(element) // 존재하면 결과 배열에 추가
setA.remove(element) // 중복 방지를 위해 해시셋에서 제거
}
}
return result
}
// 예제 실행
let A = [1, 2, 3, 4, 5]
let B = [3, 4, 5, 6, 7]
let commonElements = findCommonElements(A: A, B: B)
print(commonElements) // 출력: [3, 4, 5]
4. 시간 복잡도 분석
위의 코드에서 해시셋에 요소를 추가하는데 O(1) 시간이 소요되므로, 배열 A의 크기에 비례하여 O(n)을 소요합니다.
이후 배열 B를 순회하여 각 요소가 해시셋에 존재하는지 확인하는 것도 O(1) 시간이 소요됩니다.
따라서 전체 시간 복잡도는 O(n + m)으로, n은 배열 A의 크기, m은 배열 B의 크기입니다.
이는 원래의 O(n^2) 접근법에 비해 훨씬 효율적입니다.
결론
알고리즘 문제를 해결하는 과정에서 시간 복잡도를 분석하는 것은 필수 과정입니다.
최적의 시간 복잡도를 가진 알고리즘을 선택하는 것이 코드의 성능을 크게 향상시킬 수 있다는 점을 항상 염두에 두어야 합니다.
스위프트를 활용한 본 문제의 풀이를 통해, 시간 복잡도를 활용하여 효율적인 알고리즘을 작성하는 연습을 하셨기를 바랍니다.
앞으로도 다양한 알고리즘 문제를 풀어보면서 지속적으로 실력을 쌓아가세요!