숫자 개수 세기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. n(100,000)개의 숫자에 대해 q(100,000)번 숫자의 개수를 탐색하게 되면, O(100,000 * 100,000)으로 시간 안에 문제를 해결할 수 없음
2. 따라서 n(100,000)개의 숫자에 대해 고급 정렬을 통해 O(n log n) 시간 복잡도가 소요되고, 이후 q번의 이진탐색 O(q log n)의 시간복잡도가 소요됨
3. 이 문제는 이진탐색을 두 번 해야 하는데, 한 번은 현재 찾고자 하는 값이 mid보다 크거나 같은 경우, end를 이동 시켜 투 포인터(start와 end가 붙게 되었을 때 즉, start + 1 == end 일 때)가 맞붙었을 때, end를 반환하게 되면 해당 숫자의 가장 작은 index를 반환하게 되고,
4. 마지막 한 번은 현재 찾고자 하는 값이 mid보다 작거나 같은 경우, start를 이동 시켜 투 포인터가 맞붙었을 때, start를 반환하게 되면 해당 숫자의 가장 큰 index를 반환하게 됨으로써
5. 가장 큰 index에서 가장 작은 index의 차이를 계산하게 되면 해당 숫자가 수열에 몇개 존재하는지 알 수 있음

5. 전체 코드

//MARK: - 숫자 개수 세기

//MARK: - Framework
import Foundation

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

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

func solution() -> Void {
    //MARK: - Input
    guard let input = readLine()?.components(separatedBy: " ") else { return }
    guard let inputArray = readLine()?.components(separatedBy: " ") else { return }
    guard let inputQuestions = readLine()?.components(separatedBy: " ") else { return }
    
    let n: Int = input.map { Int($0) }[0] ?? 0
    let _: Int = input.map { Int($0) }[1] ?? 0
    let array: [Int] = inputArray.map { Int($0) ?? 0}.sorted { $0 < $1 }
    let questions: [Int] = inputQuestions.map { Int($0) ?? 0 }
    var answer: String = ""
    
    //MARK: - Process
    for question in questions {
        let maxIndex: Int = maxBinarySearch(array, 0, n, question)
        let minIndex: Int = minBinarySearch(array, -1, n - 1, question)
        
        answer += "\(maxIndex - minIndex + 1)\n"
    }
    
    //MARK: - Output
    print(answer)
}
solution()

 

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