[이진 탐색] 부품 찾기, Swift

  문제  

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개의 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

5
8 3 7 9 2
3
5 7 9

no yes yes

---

  이분 탐색 알고리즘 이용  

1. 재귀함수 이용

let n = Int(readLine()!)!
let parts = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
let m = Int(readLine()!)!
let estimate = readLine()!.split(separator: " ").map { Int($0)! }
var (start, end) = (0, parts.count)
var result = ""

estimate.forEach { part in
    result += findPart(target: part, start: 0, end: parts.count) ? "yes" : "no"
    result += " "
}

print(result)

func findPart(target: Int, start: Int, end: Int) -> Bool {
    while start <= end {
        let mid = (start + end) / 2
        if parts[mid] == target {
            return true
        } else if parts[mid] > target {
            return findPart(target: target, start: start, end: mid - 1)
        } else {
            return findPart(target: target, start: mid + 1, end: end)
        }
    }
    return false
}

 

2. 반복문 이용

let n = Int(readLine()!)!
let parts = readLine()!.split(separator: " ").map { Int($0)! }.sorted()
let m = Int(readLine()!)!
let estimate = readLine()!.split(separator: " ").map { Int($0)! }
var results = ""

estimate.forEach { part in
    results += findPart(target: part) == -1 ? "no" : "yes"
    results += " "
}

print(results)

func findPart(target: Int) -> Int {
    var (start, end) = (0, parts.count)
    while start <= end {
        let mid = (start + end) / 2
        if parts[mid] == target {
            return mid
        } else if parts[mid] > target {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return -1
}

---

  계수 정렬 이용  

1. 재귀함수 이용

let n = Int(readLine()!)!
let temps = readLine()!.split(separator: " ").map { Int($0)! }
var parts: [Int] = Array(repeating: 0, count: 1000001)
let m = Int(readLine()!)!
let estimate = readLine()!.split(separator: " ").map{ Int($0)! }
var results = ""

temps.forEach { num in
    parts[num] += 1
}

estimate.forEach { num in
    results += parts[num] == 0 ? "no" : "yes"
    results += " "
}

print(results)

---

  집합 자료구조 set 이용 

let n = Int(readLine()!)!
let temps = readLine()!.split(separator: " ").map { Int($0)! }
var parts: [Int] = Array(repeating: 0, count: 1000001)
let m = Int(readLine()!)!
let estimate = readLine()!.split(separator: " ").map{ Int($0)! }
var results = ""

temps.forEach { num in
    parts[num] += 1
}

estimate.forEach { num in
    results += parts[num] == 0 ? "no" : "yes"
    results += " "
}

print(results)

출처 | 이것이 코딩테스트다 (나동빈)