[백준] (Swift) 10815번: 숫자 카드

📌 문제

10815번: 숫자 카드

📌 풀이

풀이는 두 가지가 모두 정답으로 나왔다.

1. 이진 탐색
2. 세트(Set) 자료형

(1) 이진 탐색

처음에는 주어진 배열을 선형으로 접근했더니 ‘시간 초과’가 나와서 이진 탐색으로 바꿔서 푸니 바로 정답이 나왔다.

(2) 세트(Set) 자료형

이렇게 끝내기는 너무 아쉬워서 다른 자료형으로 풀어 보았는데, Set 자료형으로 풀면 정답이 나온다. for in을 쓸 때 Array의 시간 복잡도는 $O(n)$, Set의 시간 복잡도는 $O(1)$이다.

 

그 이유를 찾아 보니, Set는 해시 테이블을 이용해 만든 자료구조이기에 선형 탐색을 하지 않는다고 한다.

 

선형 탐색과 이진 탐색에 대한 간단한 설명은 여기를 클릭!

[CS50 2019] (컴퓨팅 사고) 알고리즘

 

 

📌 정답 코드 1 - 이진 탐색

(1) 이진 탐색 함수의 반환형을 Bool로 두었을 때

import Foundation

// 입력값을 차례로 각 변수에 할당
let N: Int = Int(readLine()!)!
var ownedCards: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted() // 이진 탐색을 위해 미리 정렬
let M: Int = Int(readLine()!)!
let numbers: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

// 배열을 이진 탐색하는 함수 정의
func binarySearch(_ array: [Int], _ target: Int) -> Bool {
    var begin: Int = 0
    var end: Int = array.count - 1
    
    // 범위를 좁혀 가며 이진 탐색
    while begin <= end {
        var mid: Int = (begin + end) / 2
        
        if array[mid] == target {
            return true // 해당 요소가 있을 경우 true을 반환
        } else if array[mid] < target {
            begin = mid + 1
        } else {
            end = mid - 1
        }
    }
    
    return false // 해당 요소가 없을 경우 false을 반환
}

// 주어진 수를 번갈아 이진 탐색하여 조건에 따라 0 또는 1을 공백으로 구분하여 출력
for number in numbers {
    if binarySearch(ownedCards, number) {
        print("1", terminator: " ")
    } else {
        print("0", terminator: " ")
    }
}

 

(2) 이진 탐색 함수의 반환형을 Int로 두었을 때

import Foundation

// 입력값을 차례로 각 변수에 할당
let N: Int = Int(readLine()!)!
var ownedCards: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }.sorted()
let M: Int = Int(readLine()!)!
let numbers: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

// 배열을 이진 탐색하는 함수 정의
func binarySearch(_ array: [Int], _ target: Int) -> Int {
    var begin: Int = 0
    var end: Int = array.count - 1
    
    while begin <= end { // 범위를 좁혀 가며 이진 탐색
        var mid: Int = (begin + end) / 2
        
        if array[mid] == target {
            return 1 // 해당 요소가 있을 경우 1을 반환
        } else if array[mid] < target {
            begin = mid + 1
        } else {
            end = mid - 1
        }
    }
    return 0 // 해당 요소가 없을 경우 1을 반환
}

// 주어진 수를 번갈아 이진 탐색하여 결괏값에 할당
for number in numbers {
    if binarySearch(ownedCards, number) == 1 {
        print("1", terminator: " ")
    } else {
        print("0", terminator: " ")
    }

 

📌 정답 코드 2 - 세트(Set) 자료형으로 풀 때

import Foundation

// 입력 값을 차례로 할당
let N = Int(readLine()!)!
let cardInput = readLine()!.split(separator: " ").map { Int($0)! }
let M = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int($0)! }

// 이미 가진 카드를 Set로 저장
var ownedCards = Set<Int>()
for card in cardInput {
    ownedCards.insert(card)
}

// 구해야 할 숫자 카드가 있는지 여부를 저장할 배열 초기화
var result: [Int] = []

for number in numbers {
    if ownedCards.contains(number) {
        result.append(1) // 이미 갖고 있는 숫자 카드면 1을 추가
    } else {
        result.append(0) // 그렇지 않으면 갖고 있는 숫자 카드면 0을 추가
    }
}

// 결과 출력
print(result.map { String($0) }.joined(separator: " "))

 

---

📌 틀린 풀이 - 선형 탐색

import Foundation

// 입력 값을 차례로 할당
let N = Int(readLine()!)!
let cardInput = readLine()!.split(separator: " ").map { Int($0)! }
let M = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int($0)! }

// 반환할 결괏값을 빈 문자열로 할당
var result: String = ""

// 이미 갖고 있는지 확인할 배열 isAlreadyHave의 값을 0으로 모두 초기화
var isAlreadyHave: [Int] = Array(repeating: 0, count: M)

// 이중 반복문으로 주어진 숫자를 이미 갖고 있는지 차례로 확인
for i in 0..<M { 
    for j in 0..<N {
        if numbers[i] == cardInput[j] {
            isAlreadyHave[i] = 1 // 있을 경우 1로 재할당
        }
    }
}

// 구한 배열을 공백으로 구분한 문자열로 변환하여 결과값에 재할당
result = isAlreadyHave.map {String($0)}.joined(separator: " ")

// 결괏값 반환
print(result)

 

📌 참고 자료

• [Python] List와 Set에서의 in 연산자 성능 비교하기.
• Why is contains() so much faster with sets than it is with arrays? – Swift – Hacking with Swift forums