Algorithm ps-2

백준 알고리즘 문제 10816번에 대한 스위프트 풀이입니다.

문제

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

첫 풀이

import Foundation

let nCount: Int = Int(readLine()!)!
let nArr: [Int] = readLine()!
    .components(separatedBy: " ")
    .map{
        Int($0)!
    }
    .sorted(by: <)

let mCount: Int = Int(readLine()!)!
let mArr: [Int] = readLine()!
    .components(separatedBy: " ")
    .map{
        Int($0)!
    }
    

var resultArr: [Int] = []

func binarySearch(_ arr: [Int], num: Int) -> Bool {
    var startPoint = 0
    var endPoint = arr.count - 1
    
    while startPoint <= endPoint {
        let mid = (startPoint + endPoint) / 2
        if arr[mid] == num {
            return true
        } else if arr[mid] <= num {
            startPoint = mid + 1
        } else if arr[mid] >= num {
            endPoint = mid - 1
        } 
    }
    return false
}

for i in 0..<mCount {
    
    if binarySearch(nArr, num: mArr[i]) {
        resultArr.append(nArr.filter{$0 == mArr[i]}.count)
    } else {
        resultArr.append(0)
    }
}

for i in 0..<resultArr.count {
    print("\(resultArr[i])",terminator: " ")
}

제가 처음 작성한 코드는 시간초과로 정답이 되지 못했습니다.
이분 탐색을 통해 N카드 더미에서 M카드 더미와 동일한 숫자가 있는지 찾았습니다. 이후 필터링을 통해 해당 카드가 몇 개 있는지 찾았으며 이 과정을 M번 반복했습니다.
시간 복잡도를 살펴보면 이분 탐색에서 O(logN)이 필요하지만 이후 필터링에서 O(N)이 필요하고 M번 반복하기 때문에 전체 시간 복잡도는 O(NM)이 되었습니다.

값을 저장하고 필터링 하는 과정에서 필터링도 동일하게 이분탐색을 구현하여 처리한다면 시간 복잡도는 O(MlogN)이 되었을 것입니다.

그러나 이분탐색 보다도 입력 받은 카드의 값과 카드의 수를 딕셔너리(해시맵)로 저장해두고 값을 가져온다면 더욱 복잡도를 줄일 수 있습니다.
입력 받은 N개의 카드 종류와 수량을 딕셔너리로 저장할 경우 시간 복잡도가 O(N)가 됩니다. 딕셔너리에서 값을 가져오는 데 필요한 복잡도는 O(1)이며 이를 M번 반복하게 되므로 결과적으로 O(M)이 됩니다. 따라서 전체 복잡도는 O(N + M)이 될 수 있습니다.

풀이 통과 코드

import Foundation

let N: Int = Int(readLine()!)! 
let numCards: [Int] = readLine()!.components(separatedBy: " ").map{ Int($0)! } // 정수형 배열로 입력 받아옴
var numDict: [Int : Int] = [:]

for num in numCards {
    numDict[num, default: 0] += 1 
}

let M: Int = Int(readLine()!)!
let queryCards: [Int] = readLine()!.components(separatedBy: " ").map { Int($0)! }

var result: [String] = []

for num in queryCards {
    if let num = numDict[num] {
        result.append("\(num)")
    } else {
        result.append("\(0)")
    }
}

print(result.joined(separator: " "))

이 문제를 해결하는 과정에서 딕셔너리를 활용하고 값을 할당하는 방법과 딕셔너리에 존재하지 않는 키를 옵셔널 언래핑과 연결지어 값을 비교하는 방법, 출력 배열을 [String]으로 선언하여 더욱 간단하게 출력하는 법을 배웠습니다.

아쉬웠던 부분

딕셔너리를 배웠지만 활용할 생각을 못했고 딕셔너리를 사용해 풀 수 있다는 걸 알게 되었어도 제대로 풀지 못했던 점이 매우 아쉬웠습니다.
그리고 이분탐색을 활용했지만 필터링 과정에서 O(N)이 필요한 방법을 사용하여 결국 전체 시간복잡도에 변화가 없었던 부분도 아쉽습니다.
알고리즘 풀이를 코드로 옮기기 전에 확실하게 계산해보는 과정이 필요하다고 느꼈습니다.