부품 탐색 문제를 여러 알고리즘으로 풀어보기 with 시간 복잡도

문제

N개의 부품 배열에서 M개의 문의 부품이 있는지 확인하여 "yes", "no"를 출력한다.

1 ≤ N ≤ 1,000,000 (100만)

1≤ M ≤ 100,000 (10만) → 최댓값 100만

이진 탐색 이용

let n = Int(readLine()!)!
var inputs = readLine()!.split(separator: " ").map { return Int($0)!}
print(n)
print(inputs)
let m = Int(readLine()!)!
let targets = readLine()!.split(separator: " ").map { return Int($0)! }

inputs.sort()
for t in targets {
    binarySearch(inputs, t)
}

func binarySearch(_ array: [Int], _ target: Int) {
    var start = 0, end = array.count - 1

    while start <= end {
        let mid = (start + end) / 2
        if array[mid] == target {
            print("yes", terminator: " ")
            return
        } else if array[mid] > target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    print("no", terminator: " ")
}

시간 복잡도

부품을 찾는 과정에서 O(M * logN) : 10만 * 20 (log 100만) = 200만

N개의 부품 정렬 과정 O(NlogN): 100만 * 20 = 2000만

즉, 200만 + 2000만 = 대략 2200만

이진 탐색 과정보다 정렬 과정에서 시간이 많이 든다.

계수 정렬 이용

let n = Int(readLine()!)!
var array = Array(repeating: 0, count: 1000001)

var inputs = readLine()!.split(separator: " ").map { return Int($0)!}
inputs.forEach {
    array[$0] = 1
}

let m = Int(readLine()!)!
let targets = readLine()!.split(separator: " ").map { return Int($0)! }

targets.forEach {
    if array[$0] == 1 {
        print("yes", terminator: " ")
    } else {
        print("no", terminator: " ")
    }
}

시간복잡도

계수 정렬의 시간 복잡도는 O(N + K) (k는 최댓값)

따라서 O(100만 + 100만) = 대략 200만

이진 탐색을 이용할 때 보다 빠르다 !

Set 이용

let n = Int(readLine()!)!

var inputs = Set(readLine()!.split(separator: " ").map { return Int($0)!})

let m = Int(readLine()!)!
let targets = readLine()!.split(separator: " ").map { return Int($0)! }

targets.forEach {
    if inputs.contains($0) {
        print("yes", terminator: " ")
    } else {
        print("no", terminator: " ")
    }
}

시간 복잡도

Set 자료구조에서의 contains 함수는 hash function을 이용하여 O(1)의 시간 복잡도로 실행된다고 한다. 따라서 O(100만)의 시간 복잡도로 구현 가능,,,?!