# 99클럽 코테 스터디 16일차 TIL - 배열 교집합 & 산 정점 찾기

피터·2025년 4월 21일
0

오늘의 문제 1: 349번 Intersection of Two Arrays
오늘의 문제 2 (보너스): 852번 Peak Index in a Mountain Array


🤔 문제 분석 및 초기 접근 (349번: 배열 교집합)

두 정수 배열 nums1nums2가 주어졌을 때, 두 배열의 교집합(intersection)을 배열로 반환하는 문제이다. 결과 배열의 요소는 유일해야 하며, 순서는 상관없다.

초기 접근: 각 배열을 Set으로 변환한 후, Setintersection 메서드를 사용하여 교집합을 구하는 방식.

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를 기록하고 있어, 혹시 더 최적화할 방법이 있는지 고민하게 되었다.


💡 문제점(?) 발견 및 개선 아이디어 (349번: 배열 교집합)

시간 복잡도 자체는 Set 생성과 intersection 연산 모두 평균적으로 O(n+m) 또는 O(min(n, m)) (구현에 따라 다름) 정도로 이미 효율적이다. 하지만 상수 시간(constant time) 최적화 여지는 있을 수 있다.

개선 아이디어: 두 배열 중 더 작은 배열을 기준으로 Set을 만들고, 다른 배열을 순회하며 해당 Set에 요소가 있는지 확인하는 방식. 이렇게 하면 Set 생성 비용과 순회 비용을 조금이라도 줄일 수 있다.


🔄 코드 개선 및 최종 제출 코드 (349번: 배열 교집합)

더 작은 배열을 기준으로 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로 줄었다! 배열 크기를 비교하여 처리 순서를 정하는 작은 최적화가 실제 성능에 영향을 미칠 수 있다는 점을 확인했다.


📚 오늘의 특강: 선형 탐색 vs 이진 탐색

오늘은 탐색 알고리즘의 기본인 선형 탐색(Linear Search)이진 탐색(Binary Search)에 대한 특강이 있었다.

  • 선형 탐색: 배열의 처음부터 끝까지 순차적으로 탐색. O(n) 시간 복잡도. 데이터 정렬 불필요.
  • 이진 탐색: 정렬된 배열에서 중간값과 비교하며 탐색 범위를 절반씩 줄여나감. O(log n) 시간 복잡도. 데이터가 반드시 정렬되어 있어야 함.

🤔 문제 분석 및 초기 접근 (852번: 산 정점 찾기)

길이가 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))을 만족하지 못한다. 또한, 정렬된 배열에서의 인덱스는 원래 배열의 정점 인덱스와 다르다.


💡 문제점 발견 및 개선 아이디어 (852번: 산 정점 찾기)

'산' 배열의 특징, 즉 정점을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순이라는 점을 이용해야 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로 좁힌다.

leftright가 만나는 지점이 바로 정점 인덱스가 된다.


🔄 코드 개선 및 최종 제출 코드 (852번: 산 정점 찾기)

위 아이디어를 바탕으로 이진 탐색 로직을 구현했다.

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 이 항상 정답은 아니다.
  • 문제의 시간 복잡도 요구사항(O(log n))을 항상 염두에 두고, 불필요한 O(n) 연산(e.g., max(), sorted(), firstIndex())을 피해야 한다.

profile
iOS 개발자입니다.

0개의 댓글