[Swift 알고리즘] 백준 10816 숫자 카드 2

해시 ○ 이분탐색 X

백준 10816 숫자 카드 2

 

이분 탐색 예제로 나와서 풀었는데, 해시로 풀어버렸다..

해시로 푸는게 훨씬 간단하고 편한거같은데..?

이분탐색은 도대체 어떻게...

 

문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다.
넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
출력
첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

해시를 이용한 풀이방법

1. 딕셔너리를 사용해 숫자 카드에 적힌 숫자들의 중복 개수를 먼저 구해준다. key는 숫자, value는 중복 개수

2. M개의 정수에 대해 하나씩 돌아가며 딕셔너리에 해당 정수를 key 로 가진 값이 있다면 해당 값을, 없다면 0 을 넣어준다.

 

해시 126912KB 656ms

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

var dict = [Int:Int]()
var result = [Int]()
//1
for num in nArray {
    dict.updateValue((dict[num] ?? 0) + 1, forKey: num)
}
//2
for num in mArray {
    result.append(dict[num] ?? 0)
}

print(result.map{ String($0) }.joined(separator: " "))

 

이분탐색 - while 반복문을 이용한 풀이방법

 

113900KB 748ms

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

nArray.sort()
var result = [Int]()

for num in mArray {
    let s = lowerBound(nArray, num)
    let e = upperBound(nArray, num)
    result.append(e - s)
}
print(result.map{ String($0) }.joined(separator: " "))

func lowerBound(_ arr: [Int], _ k: Int) -> Int {
    var s = 0
    var e = arr.count

    while s < e {
        let mid = (s + e)/2
        if arr[mid] < k {
            s = mid + 1
        } else {
            e = mid
        }
    }
    return s
}

func upperBound(_ arr: [Int], _ k: Int) -> Int {
    var s = 0
    var e = arr.count

    while s < e {
        let mid = (s + e)/2
        if arr[mid] <= k {
            s = mid + 1
        } else {
            e = mid
        }
    }
    return s
}

 

이분탐색 upperbound lowerbound 이용해서 푸는 방법 참고 : 

https://www.acmicpc.net/source/50772524

 

이분탐색 - 재귀 이용한 풀이방법

왜 안되는거지..? 테스트 케이스 통과 잘 되는데 백준 채점하면 자꾸 시간초과 뜬다.. 왜지..?

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

nArray.sort()
var result = [Int]()

for num in mArray {
    let s = lowerBound(num, 0, N)
    let e = upperBound(num, 0, N)
    result.append(e - s)
}
print(result.map{ String($0) }.joined(separator: " "))

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

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