[Swift 알고리즘] 백준 1920 수 찾기

백준 1920 수 찾기

 

binary search 이분탐색 1단계

문제 :
 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력 :
 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)
 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]
 다음 줄에는 M(1 ≤ M ≤ 100,000)
 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.
 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.
출력 :
 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

1차 시도 시간초과 실패 

.contains 의 시간복잡도는 O(n)으로 다음과 같이 for문 안에 사용하게 되면 최악의 경우, 경우의 수는 N*M이 된다.

주어진 N과 M의 범위가 최대 10만이므로 시간복잡도는 O(n^2) 으로 시간 초과가 뜬다.

let N = Int(readLine()!)!
var nArray = readLine()!.split(separator: " ").map { Int($0)! }
let M = Int(readLine()!)!
let mArray = readLine()!.split(separator: " ").map { Int($0)! }

for i in 0..<mArray.count {
    if nArray.contains(mArray[i]) {
        print(1)
    } else {
        print(0)
    }
}

 

이분 탐색(이진 탐색)으로 시간복잡도를 줄일 수 있다. 

1. 시작, 중간, 끝 값을 이용해 이진탐색을 할 수 있도록 배열을 정렬해준다. 

2. start 값을 0으로, end 값을 배열크기 - 1 로 초기화해준다. 

3. start 값이 end 값보다 작은 경우 재귀함수 또는 반복문을 통해 이진탐색을 구현해준다.

  3-1. mid 값은 소수점을 버린 start와 end의 중간값이다.

  3-2. 배열의 중간값이 목표값(k) 보다 크면 뒤의 절반을 볼 필요가 없기 때문에 앞의 절반만 남긴다. e = mid

  3-3. 배열의 중간값이 목표값(k) 보다 작으면 앞의 절반을 볼 필요가 없기 때문에 뒤만 남긴다. s = mid + 1

4. start 값과 end 값이 같아지는 경우, 탈출조건을 설정해준다.

  4-1. 배열에서 마지막 남은 수가 목표값(k)와 일치하면 1을 리턴한다.

  4-2. 일치하지 않으면 배열 내에 존재하지 않는 것으로 0을 리턴한다. 

 

이렇게 하면 O(n) 반복문과 이분탐색 O(log n)을 중첩하여, 시간복잡도는 O(n log n) 이 된다. 

 

이분탐색 - 재귀함수 사용

nArray = nArray.sorted()

for i in 0..<M {
    print(binarySearch(mArray[i], 0, N - 1))
}

func binarySearch(_ k: Int, _ s: Int, _ e: Int) -> Int {
    if s == e {
        if nArray[s] == k { return 1 }
        else { return 0 }
    }
    let mid = (s + e)/2
    if nArray[mid] >= k { return binarySearch(k, 0, mid) }
    else { return binarySearch(k, mid + 1, e) }
}

 

이분탐색 - while 반복문 사용

nArray.sort()

for i in 0..<M {
    print(binarySearch(mArray[i]))
}

func binarySearch(_ k: Int) -> Int {
    var start = 0
    var end = N - 1

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

 

 

 

---

참고 :

https://sapjilkingios.tistory.com/86