[SWIFT]백준1920 수찾기/이진탐색/시간복잡도

---

<정답코드>

import Foundation
//1920 수찾기
//출처)https://sapjilkingios.tistory.com/86
//모범답안인듯하다 이해했고 다음에 이렇게 풀수있을거같다
let n = Int(readLine()!)!
var firstArr = readLine()!.split(separator: " ").map{Int($0)!}

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

firstArr.sort()

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

    while start <= end {
        let mid = (start + end) / 2
            if firstArr[mid] == target {
                return 1
            }else if firstArr[mid] > target {
                end = mid - 1
            }else if firstArr[mid] < target {
                start = mid + 1
            }
        }
        return 0
}


for i in 0..<m {
    print(binarySearch(firstArr, secondArr[i]))
}

이문제.. 정말 할말이 많다.

알아야 할 지식은 시간복잡도와 이진탐색 !

---

<시간복잡도>

출처) https://hwan1402.tistory.com/106

이렇듯 시간복잡도가 효율적인 순서 (뒤로갈수록 느려짐)

O(log n) == O(1) 

O(n)

O(n log n)

O(n^2)

O(2^n)

O(n!)

---

<이진탐색이란>

출처) https://velog.io/@devjade/이진탐색-binary-search

전체에서 배열에 있는 중간에 있는 값을 기준으로

그값과 찾는값을 비교 후, 

범위를

   중간값이 더 크면 중간값+1...마지막인덱스

   중간값이 더 작으면 0..<중간값

수정한다

이렇게 반복하여 중간에있는 값이 찾는값과 같다면 1,

끝까지 반복했는데도 다르다면 0을 리턴한다

---

<풀기위해 노력했던 내 코드들>

//import Foundation
////1920 수찾기 에라토스테네스의 체로 풀어봤는데 범위가 -2^31 보다 크거나 같고 2^31보다 작다에서
////마이너스때문에 걸리기 때문에 이렇게는 못푼다 ! (O(1)제일 빠르지만 범위때문에 패스)
//let _ = Int(readLine()!)!
//var samplearr = Array(repeating: false, count: 100000/*여기서문제가생김*/)
//var sampleinput = readLine()!.split(separator: " ").map { Int(String($0))! }
//for i in sampleinput{
//    samplearr[i] = true
//}
//let _ = Int(readLine()!)!
//var input = readLine()!.split(separator: " ").map{ Int(String($0))! }
//for i in input{
//    (samplearr[i] == true) ? print("1") : print("0")
//}

 

//import Foundation
////1920 수 찾기 얘는 시간초과뜸(contain함수는 O(n)이라 얘도 빠른편인데 왜 ....)
//let _ = Int(readLine()!)!
//var sampleInput = readLine()!.split(separator: " ").map{Int(String($0))!}
//let times = Int(readLine()!)!
//var input = readLine()!.split(separator: " ").map{Int(String($0))!}
//for i in 0..<times{
//    sampleInput.contains(input[i]) ? print("1") : print("0")
//}

 

////1920 수찾기 이진탐색을 이용하여 찾아보기..!(시간복잡도 O(nlog))
////이진탐색함수만들기(블로그참고하고 컨닝하고 따라하고,, 문제에 맞게 수정하구,,)
////와.. 얘도 시간초과 . 왜..?
//import Foundation
//func binaryFunc(_ arr: [Int], _ num: Int) -> Bool{
//    let mid = arr.count/2
//    if(arr.count == 1){
//        return (arr.first == num) ? true : false
//    }else if mid == 0{
//        return false
//    }else if (arr[mid] == num){
//        return true
//    }
//
//    let range = arr[mid] > num ? (0..<mid) : ((mid+1)..<arr.count)
//
//    return binaryFunc(Array(arr[range]), num)
//}
//
//let _ = Int(readLine()!)!
//var sampleInput = readLine()!.split(separator: " ").map{Int(String($0))!}
//let _ = Int(readLine()!)!
//var input = readLine()!.split(separator: " ").map{Int(String($0))!}
//sampleInput.sort()
//for i in input{
//    binaryFunc(sampleInput, i) ? print("1") : print("0")
//
//}

---

탐색관련한 방법들은 정말 얕게 알고있는데 (어느탐색이 있다더라 정도만)

시간복잡도에 대해서는 한번도 생각해보지 않았다.

이번 기회에 시간복잡도에 관한 내용을 조금이나마 알게 되어 기쁘다.

 

+이번주 내로 탐색 종류들 정리해서 포스팅을 해야쥐