1920번 수 찾기 - swift

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

---

처음에는 N과 M 배열을 각각 만든 후에 

M배열의 요소를 N배열에 하나하나 모두 비교해서 참, 거짓을 리턴하려 시도 했었다. 하지만 시간도 오래 걸릴 뿐더러 더 좋은 자료구조 방법이 있었다. 

 

그것은 이분 탐색이다. 이분 탐색이 뭔지는 아래 링크에 올려놨으니 살펴보자. 

 

https://zerostar0809.tistory.com/10?category=1080283 

6. 정렬(sort)

 

 

 

 

import Foundation

var N = Int(readLine()!)!  // 첫 줄
var arrNum1: [Int] = [] // 배열 만들기.
arrNum1 = readLine()!.split(separator: " ").map{Int(String($0))!} // 배열안에 N만큼의 정수 넣기.
arrNum1.sort() // 탐색하기 용이하게 정렬을 해놓는게 좋다.


var M = Int(readLine()!)! // 두 번째 입력.
var arrNum2: [Int] = [] //M의 배열 만들기.
arrNum2 = readLine()!.split(separator: " ").map{Int(String($0))!}

var result = [Int]() // 결과 배열 만들기. 여기에 결과를 받아서 한글자씩 출력할 것임.

for i in 0..<M {
    result.append(binarySearch(arrNum1, arrNum2[i]))
}

for i in 0..<result.count{
    print(result[i])
}



//func binarySearch(_ array: [Int], num: Int) -> Bool {
//    if array.count == 1 {
//        return array[0] == num ? true : false
//    }
//    let mid = array.count / 2
//    let range = array[mid] > num ? (0..<mid) : ((mid+1)..<array.count)
//
//
//    return binarySearch(Array(array[range]), num: num)
//} // 이분 탐색. (재귀함수로 구현)


func binarySearch(_ array: [Int], _ num: Int) -> Int {
    var start = 0
    var end = (array.count - 1)
    
    while start <= end {
        let mid = (start + end) / 2
        
        if array[mid] == num {return 1} // 배열의 중간 요소가 내가 찾는 숫자라면 true를 반환한다. (정수로는 1)
        
        if array[mid] > num { // 내가 찾는 숫자가 배열의 중간값 보다 왼쪽에 있다면
            end = mid - 1 // 중간을 기준으로 왼쪽으로 움직인다.
        } else {
            start = mid + 1 // 그게 아니라면 오른쪽으로 움직인다.
        }
    }
    return 0
}

먼저 입력 받을 N을 만들자. 그리고 입력 받은 수 만큼 배열을 작성하자. 이 것까진 M차례와 동일하게 가져간다. 

 

하지만 이분 탐색을 사용할 것이기 때문에 N배열을 만들때 .sort()를 이용해서 정렬해준다. M은 하지 않아도 상관없다. 

 

최종적으로 결과가 들어갈 배열을 만들고 이중 탐색 함수를 구현해서 이용한다.