[Swift] BOJ 1920 수 찾기

BOJ 1920 수 찾기

 

✅ 이진탐색을 구현하는 문제이다. 

아니 이진탐색 그 자체이다.

 

✅ 코드

 

자료구조와 함께 추가하였다. 이진 탐색 포스팅은 최대한 빨리 하도록하자 

 

import Foundation

/// 오름차순으로 정렬 된 리스트에서 item의 index를 반환합니다. 없으면 -1
func binarySearchForAscending<T: Comparable>(array: [T], item: T) -> Int {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        let guess = array[mid]
        if guess == item {
            return mid
        } else if guess > item {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return -1
}

        _ = Int(readLine()!)!
        var searchList = [Int]()
        var input = readLine()!.components(separatedBy: " ").map { Int($0)! }
        
        input.forEach { searchList.append($0) }
        
        _ = Int(readLine()!)!
        var numberList = [Int]()
        input = readLine()!.components(separatedBy: " ").map { Int($0)! }
        
        input.forEach { numberList.append($0) }
       
        searchList.sort(by: <)
//        print(searchList) // 기준
//        print(numberList) // 찾아야 하는 기준 숫자
        
        var answer = [Int]()
        numberList.forEach {
            let a = binarySearchForAscending(array: searchList, item: $0)
            if a == -1 {
                answer.append(0)
            } else {
                answer.append(1)
            }
        }
        
        answer.forEach {
            print($0)
        }

 

 

(참고)

https://babbab2.tistory.com/104

Swift) 탐색 :: 이진 탐색(Binary Search) 이해하기

https://icksw.tistory.com/27

[백준] 1920번 수 찾기[Swift]