구간의 합집합

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• i의 범위를 보더라도 완전탐색으로 절대 시간안에 문제를 해결할 수 없는 것을 알 수 있음
• 따라서 더 효율적인 탐색 알고리즘으로 문제를 해결해야 하고, 각각의 시작점과 끝점을 저장하는 2차원 배열을 구성하거나,
• 각각을 1차원 배열에 저장하는 방법도 있음, 이때 시작점 끝점을 입력받아 각각 배열에 저장할 때 O(n)으로 저장해야 하는 것에 유의 해야함
• 모든 시작점과 끝점의 정보가 저장되어 있는 배열을 O(n)의 시간복잡도로 최소 시작점, 최대 끝점을 각각 구하고,
• 최소 시작점부터 최대 끝점에 대해 이진탐색을 통해 문제를 해결할 수 있음
• 모든 구간의 합집합에 대해 O(n)의 시간 복잡도로 최소 시작점에서 최대 끝점 범위에 해당하는 각각의 숫자의 위치를 알아낼 수 있음
• 최소 시작점에서 최대 끝점에 대해 중간 값이 각각의 구간의 끝점보다 크면 각 구간의 끝점과 시작점의 차이를 통해 현재 중간 값보다 작은 수의 개수를 알 수 있고,
• 중간 값보다 각 구간의 끝점이 작거나 같다면, 중간 값이 시작점보다 작거나 같으면 작은 숫자가 없고, 중간 값이 시작점 보다 크다면 중간 값과 시작점의 차이를 통해 작은 개수를 알 수 있음
• 위 과정을 통해 얻은 작은 수의 개수가 해당 수의 위치임을 알 수 있고, 이 수를 매개변수로 삼아 이진탐색을 하게 되면 
• O(n log n)의 시간복잡도로 문제를 해결할 수 있음(이때, 위치에 대한 값은 Int64 자료형으로 저장 해주어야 함)

5. 전체 코드

//MARK: - 구간의 합집합

//MARK: - Framework
import Foundation

//MARK: - Function
func getMax(_ array: [[Int]], _ n: Int) -> Int {
    var result: Int = array[0][1]
    for i in 1..<n {
        result = array[i][1] > result ? array[i][1] : result
    }
        
    return result
}

func getMin(_ array: [[Int]], _ n: Int) -> Int {
    var result: Int = array[0][0]
    for i in 1..<n {
        result = array[i][0] < result ? array[i][0] : result
    }
    
    return result
}

func getOrder(_ array: [[Int]], _ n: Int, _ number: Int) -> Int64 {
    var result: Int64 = 0
    for i in 0..<n {
        if number > array[i][1] {
            result += Int64(array[i][1] - array[i][0] + 1)
        } else {
            result += number <= array[i][0] ? 0 : Int64(number - array[i][0])
        }
    }
    
    return result
}

func binarySearch(_ array: [[Int]], _ n: Int, _ start: Int, _ end: Int, _ value: Int64) -> Int {
    if start + 1 >= end {
        return start
    }
    
    let mid: Int = (start + end) / 2
    return getOrder(array, n, mid) <= value ? binarySearch(array, n, mid, end, value) : binarySearch(array, n, start, mid, value)
}

func solution() -> Void {
    //MARK: - Input
    guard let n: Int = Int(readLine() ?? "0") else { return }
    
    var array: [[Int]] = Array(repeating: Array(repeating: 0, count: 2), count: n)
    for i in 0..<n {
        guard let input = readLine()?.components(separatedBy: " ") else { return }
        let s: Int = input.map { Int($0) }[0] ?? 0
        let e: Int = input.map {Int($0) }[1] ?? 0
        
        array[i][0] = s
        array[i][1] = e
    }
    
    guard let i: Int64 = Int64(readLine() ?? "0") else { return }
    let start: Int = getMin(array, n)
    let end: Int = getMax(array, n)
    
    //MARK: - Process
    let result: Int = binarySearch(array, n, start, end + 1, i)
    
    //MARK: - Output
    print(result)
    
}
solution()

 

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