💥배열이 오름차순으로 정렬되어있다?💥
💥순차정렬보다 이분탐색 쓰는 건 아닌지 생각해보면 좋다!💥

---

---

1920

1920 수 찾기
답도 나오고 이분탐색 방식으로도 풀었는데...
채점하면 런타임에러네ㅠㅠ 왜그러지ㅠㅠ

import Foundation

let n = Int(readLine()!)

var nArr = readLine()!.split(separator: " ").map { Int(String($0))! }

nArr.sort()

let m = Int(readLine()!)!

let mArr = readLine()!.split(separator: " ").map { Int(String($0)) }


func binarySearch(_ start: Int, _ end: Int, _ mData: Int) -> Int {
    var result = 0  //아직 못찾았을 때
    
    var start = start
    var end = end
    
    while start < end {
        
        let mid = start + (end - start) / 2
        
        if nArr[mid] == mData {
            result = 1  //찾았을 때
            return result
        } else if nArr[mid] < mData {
            start = mid + 1
        } else {
            end = mid
        }
        
        
    }
    
    return result
}

for mData in mArr {
    print(binarySearch(0, mArr.count, mData!))
}

import Foundation

let n = Int(readLine()!)

var nArr = readLine()!.split(separator: " ").map { Int(String($0))! }

nArr.sort()    // 이분탐색은 정렬되어이 있어야하기 때문에

let m = Int(readLine()!)!

let mArr = readLine()!.split(separator: " ").map { Int(String($0)) }


func binarySearch(_ start: Int, _ end: Int, _ mData: Int) -> Int {
    var start = start
    var end = end
    
    while start < end {
        
        let mid = start + (end - start) / 2
        
        if nArr[mid] == mData {
            return mid
        } else if nArr[mid] < mData {
            start = mid + 1
        } else {
            end = mid
        }
    }
    
    return -1
}

for i in 0..<mArr.count {
    let result = binarySearch(0, mArr.count, mArr[i]!)
    if result == -1 {
        print(0)
    } else {
        print(1)
    }
}

---

1654

1654 랜선 자르기

파라메트릭 서치 Parametric Search

: 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제
: 최적화 문제를 결정 문제로 바꾸어 해결하는 기법
최적화 문제: 최대한 높이거나 최대한 낮추거나
결정 문제: 예/아니오 로 답하는 문제

import Foundation

let kn = readLine()!.split(separator: " ").map { Int(String($0))! }
let k = kn[0]   //랜선의 개수
let n = kn[1]   //필요한 랜선의 개수    k<=n

var kArr = [Int]()
for _ in 0..<k {
    kArr.append(Int(readLine()!)!)
}

func binarySearch(_ start: Int, _ end: Int) {
    var start = start
    var end = end

    while start <= end {
        
        var numberOfLan = 0
        let mid = start + (end - start) / 2
        
        for data in kArr {
            numberOfLan += data / mid
        }
        
        if numberOfLan >= n {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    
    print(end)
}

let kMax = kArr.max()!   // 랜선의 길이 1 ~ kMax
binarySearch(1, kMax)

//func binarySearch( start: Int, end: Int, target: Int) -> [Int] {
// var start = start
// var end = end
//
// while start <= end {
// var mid = start + (end - start) / 2
//
// if mArr[mid] == target {
// return mArr.filter{ in mArr.contains(target) }
// } else if mArr[mid] > target {
// start = mid + 1
// } else {
// end = mid - 1
// }
// }
//
// return [0]
//}
//
//var answer = Int
//for number in nArr {
// print(binarySearch(0, mArr.count-1, number))
//}

---

10816

10816 숫자 카드 2
10 9 -5 2 3 4 5 -10 갖고 있는 카드일 때
3 0 0 1 2 0 0 2
예를 들어 10은 3개있는 건데...
어떻게 구하지ㅠ

import Foundation

let m = Int(readLine()!)!
var mArr = readLine()!.split(separator: " ").map{ Int(String($0))! }	// 전체 카드의 집합
mArr.sort() //정렬한 다음에 이진탐색 써야지~

let n = Int(readLine()!)!
let nArr = readLine()!.split(separator: " ").map{ Int(String($0))! }	// 찾을 카드의 집합

let filteredArr = mArr.filter{ nArr.contains($0) }  //[-10, -10, 2, 3, 3, 10, 10, 10]