[Swift]BOJ-10815

BOJ-10815, 숫자 카드

문제 📑
https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

문제 정리 ▾

BOJ-10815

• N개의 정수 리스트(standardLst)가 있고, M개의 정수 리스트(haveLst)가 있는데 haveLst 정수 중 standardLst에 포함된 정수가 있으면 "1", 없으면 "0"을 출력하는 프로그램

 

접근 🚶🏻

나의 생각 ▾

• 저번 1290번 문제와 같은 유형이라 생각했다. (이진 탐색)

첫 번째 방법 ▾

import Foundation

let n = Int(String(readLine()!))!
let standardLst = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted(by: <)

let m = Int(String(readLine()!))!
let haveLst = readLine()!.split(separator: " ").map{ Int(String($0))! }

func binarySearch(_ arr: [Int], _ target: Int) -> Int {
    var sIdx = 0
    var eIdx = standardLst.count

    while sIdx <= eIdx {
        let mid = (sIdx + eIdx) / 2
        if arr[mid] == target {
            return 1
        } else if arr[mid] > target {
            eIdx = mid - 1
        } else if arr[mid] < target {
            sIdx = mid + 1
        }
    }

    return 0
}

for i in 0..<haveLst.count {
    print(binarySearch(standardLst, haveLst[i]), terminator: " ")
}

• 그러나 결과는 런타임 에러..
• Swift로 알고리즘을 푸는 경우가 좀 드물어서 그런지 런타임 에러 사항에 Swift 관련 사항도 없었다.
• 그래서 While문 대신 재귀 함수로 풀어보기로 했다.

 

두 번째 방법 ▾

import Foundation

func solution() {
    let n = Int(String(readLine()!))!
    let standardLst = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted(by: <)
    let _ = Int(String(readLine()!))!
    let haveLst = readLine()!.split(separator: " ").map{ Int(String($0))! }
    
    var result = [String]()
    
    for i in haveLst {
        if binarySearch(0, n - 1, arr: standardLst, target: i) {
            result.append("1")
        } else {
            result.append("0")
        }
    }
    print(result.joined(separator: " "))
}

func binarySearch(_ sIdx: Int, _ eIdx: Int, arr: [Int], target: Int) -> Bool {
    var result = false
    if sIdx > eIdx {
        return false
    }
    let mid = (sIdx + eIdx) / 2
    if arr[mid] < target {
        result = binarySearch(sIdx + 1, eIdx, arr: arr, target: target)
    } else if arr[mid] > target {
        result = binarySearch(sIdx, eIdx - 1, arr: arr, target: target)
    } else {
        return true
    }
    return result
}

solution()

• 이 역시 마찬가지로 런타임 에러가 떴다..
• 이유를 모르겠다...
• 결과는 두 코드 모두 잘 나왔다.

 

결과 화면 ▾

BOJ-10815

Additional 📂

• 런타임 에러가 무엇인지 정확히 모르겠다.
• 하지만 분명 코드에 문제가 있거나 출제자의 의도가 아닌 것으로 판단이 된다.
• 알고리즘 분류에는 "이분 탐색"이라고 명시는 되어있지만 모르겠다.
• 그래도 이번 문제를 통해 확실하게 이진 탐색을 공부할 수 있었다.
• 추가적으로 해결책이 생기면 적어두어야겠다.