오늘의 문제 1: 349번 Intersection of Two Arrays
오늘의 문제 2 (보너스): 852번 Peak Index in a Mountain Array
두 정수 배열 nums1
과 nums2
가 주어졌을 때, 두 배열의 교집합(intersection)을 배열로 반환하는 문제이다. 결과 배열의 요소는 유일해야 하며, 순서는 상관없다.
초기 접근: 각 배열을 Set
으로 변환한 후, Set
의 intersection
메서드를 사용하여 교집합을 구하는 방식.
class Solution {
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
let set1 = Set(nums1)
let set2 = Set(nums2)
return Array(set1.intersection(set2))
}
}
이 코드는 문제없이 통과했지만, 실행 시간이 4ms로 측정되었다. LeetCode 제출 통계를 보니 상위 85%는 0ms를 기록하고 있어, 혹시 더 최적화할 방법이 있는지 고민하게 되었다.
시간 복잡도 자체는 Set
생성과 intersection
연산 모두 평균적으로 O(n+m) 또는 O(min(n, m)) (구현에 따라 다름) 정도로 이미 효율적이다. 하지만 상수 시간(constant time) 최적화 여지는 있을 수 있다.
개선 아이디어: 두 배열 중 더 작은 배열을 기준으로 Set
을 만들고, 다른 배열을 순회하며 해당 Set
에 요소가 있는지 확인하는 방식. 이렇게 하면 Set
생성 비용과 순회 비용을 조금이라도 줄일 수 있다.
더 작은 배열을 기준으로 Set
을 만들고, 다른 배열을 순회하면서 교집합을 찾는 로직으로 수정했다. 결과 저장 시에도 중복을 피하기 위해 Set
을 사용했다.
func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
// 더 작은 배열과 더 큰 배열을 구분
let (smaller, bigger) = nums1.count <= nums2.count ? (nums1, nums2) : (nums2, nums1)
// 더 큰 배열로 Set을 생성 (contains 연산을 위해)
let biggerSet = Set(bigger)
var resultSet = Set<Int>() // 결과 저장을 위한 Set
// 더 작은 배열을 순회하며 큰 배열 Set에 있는지 확인
for num in smaller {
if biggerSet.contains(num) {
resultSet.insert(num) // 교집합 요소를 결과 Set에 추가
}
}
return Array(resultSet) // 결과 Set을 배열로 변환하여 반환
}
이 코드로 제출하니 실행 시간이 1ms로 줄었다! 배열 크기를 비교하여 처리 순서를 정하는 작은 최적화가 실제 성능에 영향을 미칠 수 있다는 점을 확인했다.
오늘은 탐색 알고리즘의 기본인 선형 탐색(Linear Search)과 이진 탐색(Binary Search)에 대한 특강이 있었다.
길이가 3 이상인 '산' 배열 arr
이 주어진다. 이 배열은 특정 인덱스 i
까지는 arr[0] < arr[1] < ... < arr[i]
로 증가하고, 그 이후로는 arr[i] > arr[i+1] > ... > arr[arr.length - 1]
로 감소하는 특징을 가진다. 이 '정점(peak)'에 해당하는 인덱스 i
를 찾는 문제이다. O(log n) 시간 복잡도로 풀어야 한다.
초기 접근 (잘못된 방향): 배열의 최댓값을 찾고(arr.max()
), 배열을 정렬한 뒤, 정렬된 배열에서 최댓값의 인덱스를 이진 탐색으로 찾는 방식.
// 잘못된 접근 방식
func peakIndexInMountainArray_initial(_ arr: [Int]) -> Int {
// 1. 최댓값 찾기 (O(n))
guard let peakValue = arr.max() else { return -1 }
// 2. 배열 정렬 (O(n log n))
let sortedArray = arr.sorted()
// 3. 정렬된 배열에서 이진 탐색 (O(log n)) -> 하지만 이건 원래 배열의 인덱스가 아님!
// ... (기존 코드의 binarySearch 함수) ...
// return binarySearch(sortedArray, target: peakValue) // 잘못된 결과 반환
// 4. 최댓값의 원래 인덱스 찾기 (O(n))
return arr.firstIndex(of: peakValue) ?? -1 // 결국 O(n)이 됨
}
이 방식은 최댓값을 찾거나 정렬하는 과정에서 이미 O(n) 또는 O(n log n)의 시간 복잡도를 가지므로 문제 요구사항(O(log n))을 만족하지 못한다. 또한, 정렬된 배열에서의 인덱스는 원래 배열의 정점 인덱스와 다르다.
'산' 배열의 특징, 즉 정점을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순이라는 점을 이용해야 O(log n)이 가능하다. 이진 탐색을 변형하여 적용할 수 있다.
개선 아이디어: 이진 탐색의 mid
인덱스를 기준으로 arr[mid]
와 arr[mid + 1]
을 비교한다.
arr[mid] < arr[mid + 1]
이면, 현재 mid
는 오르막길에 있으므로 정점은 mid
보다 오른쪽에 있다. 따라서 탐색 범위를 left = mid + 1
로 좁힌다.arr[mid] > arr[mid + 1]
이면, 현재 mid
는 내리막길에 있거나 mid
자체가 정점일 수 있다. 따라서 정점은 mid
또는 그 왼쪽에 있다. 탐색 범위를 right = mid
로 좁힌다.left
와 right
가 만나는 지점이 바로 정점 인덱스가 된다.
위 아이디어를 바탕으로 이진 탐색 로직을 구현했다.
func peakIndexInMountainArray(_ arr: [Int]) -> Int {
var left = 0
var right = arr.count - 1
// left와 right가 같아질 때까지 반복
while left < right {
let mid = (right + left) / 2 // 오버플로우 방지
// mid가 오르막길에 있는 경우 (정점은 오른쪽에 있음)
if arr[mid] < arr[mid + 1] {
left = mid + 1
}
// mid가 내리막길 또는 정점인 경우 (정점은 mid 또는 왼쪽에 있음)
else {
right = mid // mid도 정점 후보이므로 right = mid - 1 이 아님
}
}
// left와 right가 만나는 지점이 정점 인덱스
return left
}
이 코드는 배열의 정렬 없이, '산' 배열의 특성을 활용한 이진 탐색으로 O(log n) 시간 복잡도를 만족한다.
left = mid + 1
, right = mid
)을 문제 상황에 맞게 정확히 설정해야 함을 다시 한번 확인했다. right = mid - 1
이 항상 정답은 아니다.max()
, sorted()
, firstIndex()
)을 피해야 한다.