[백준/Swift] 1764번: 듣보잡

 

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

1764번: 듣보잡

 

이분탐색으로 간단하게 해결할 수 있는 문제.

N이 작으면 이분탐색보다는 선형탐색이 더 낫지만 500,000까지 가므로 이분탐색으로 해줬다.

듣지도 못한 사람의 명단을 String 배열로 만들어줬고, 보지도 못한 사람들을 하나씩 받아서 이분탐색으로 듣지도 못한 사람 명단에 이름이 있는지 확인해 줬다.

 

import Foundation

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
let n = input[0]
let m = input[1]
var dontListen = [String]()
var answer = [String]()

for _ in 0..<n {
    dontListen.append(readLine()!)
}
dontListen = dontListen.sorted()

for _ in 0..<m {
    let dontSee = readLine()!
    var left = 0
    var right = n-1
    while left <= right {
        let mid = (left + right) / 2
        if dontListen[mid] == dontSee {
            answer.append(dontSee)
            break
        }else if dontListen[mid] < dontSee {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
}
print(answer.count)
answer.sorted().forEach {
    print($0)
}