숫자박스

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. N(300,000)개의 숫자에 대해 M(500,000)번의 탐색을 하게 되면, 300,000 * 500,000 = 150,000,000,000 이므로,
2. 시간안에 문제를 해결할 수 없음. 따라서 다른 탐색 알고리즘을 사용하여 문제를 해결해야 함
3. N(300,000)개의 숫자에 대해 정렬을 하게 되면 합병 정렬, 퀵정렬 등 고급 정렬을 통해 O(N log N)의 시간복잡도로 정렬을 할 수 있고,
4. 이미 정렬된 알고리즘에 대해 이진탐색을 하게 되면 O(log N)이고 이를 M(500,000)번 반복하게 되면,
5. O(N log N) + O(M log N)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 숫자박스

//MARK: - Framework
import Foundation

//MARK: - Function
func binarySearch(_ array: [Int], _ start: Int, _ end: Int, _ value: Int) -> Bool {
    if start >= end {
        return array[start] == value ? true : false
    }
    
    let mid = (start + end) / 2
    if array[mid] == value {
        return true
    }
    
    return array[mid] < value ? binarySearch(array, mid + 1, end, value) : binarySearch(array, start, mid - 1, value)
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let inputArray = readLine()?.components(separatedBy: " ") else { return }
    guard let _: Int = Int(readLine() ?? "0") else { return }
    guard let inputCandidates = readLine()?.components(separatedBy: " ") else { return }
    
    let array: [Int] = inputArray.map { Int($0) ?? 0 }.sorted { $0 < $1 }
    let candidates: [Int] = inputCandidates.map { Int($0) ?? 0 }
    var answer: String = ""
    
    //MARK: - Process
    for candidate in candidates {
        answer += binarySearch(array, 0, N - 1, candidate) ? "\(1)\n" : "\(0)\n"
    }
    
    //MARK: - Output
    print(answer)
    
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.