백준 - 1764 듣보잡 - Swift

백준 1764 듣보잡

문제 : https://www.acmicpc.net/problem/1764

1. Set으로 푼다
2. binarySearch로 푼다

코드 길이는 Set가 더 짧고
메모리와 시간은 binarySearch가 더 효율적이다

Set :

let input = readLine()!.split(separator: " ").map{Int($0)!}
var set1 = Set<String>()
var set2 = Set<String>()
(0..<input[0]).forEach{ _ in
    set1.insert(readLine()!)
}
(0..<input[1]).forEach { _ in
    set2.insert(readLine()!)
}
let arr = set1.intersection(set2).sorted()
print(arr.count)
print(arr.joined(separator: "\n"))

binarySearch :

let input = readLine()!.split(separator: " ").map{Int($0)!}
var arr: [String] = []
for _ in 0..<input[0]{
    arr.append(readLine()!)
}
arr.sort()
var count = 0
var res: [String] = []
for _ in 0..<input[1]{
    let read = readLine()!
    if binarySearch(array: arr, item: read){
        count += 1
        res.append(read)
    }
}
print(count)
res.sort()
res.forEach{print($0)}

func binarySearch(array: [String], item: String) -> Bool {
    var low = 0
    var high = array.count - 1
    
    while low <= high {
        let mid = (low + high) / 2
        let guess = array[mid]
        if guess == item {
            return true
        } else if guess > item {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return false
}