글 읽기 - [swift] - 1920 수 찾기 문제 이분탐색 관련 시간초과

santoo 2년 전 0

맨 처음엔 이분탐색 알고리즘을 짜서 배열을 반 씩 줄여줬습니다. 그런데 이러면 배열값이 다시 할당되면서 시간복잡도가 증가할거라 생각하여 인덱스를 이용하여 풀었지만, 역시 16%에서 시간초과가 납니다. 더 효율적인 방법이 있을까요? 아래는 인덱스로 짠 이분탐색 코드입니다. 감사합니다.

readLine()!
let a = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted()
readLine()!
let b = readLine()!.split(separator: " ").map{ Int(String($0))! }
for i in b {
    print(search(i, 0, a.count - 1))
}
func search(_ what: Int, _ start: Int, _ end: Int) -> Int {
    let pivot = (start + end) / 2
    if start > end {
        return 0
    }
    if what < a[pivot] {
        return search(what, start, pivot)
    } else if what > a[pivot] {
        return search(what, pivot + 1, end)
    } else if what == a[pivot] {
        return 1
    }
    return 0
}

fbfbf1 2년 전 0

14번째 줄에서 search(what,start,pivot - 1)로 하면 맞았습니다 처리됩니다.

어차피 pivot은 봤기 때문에 다시 그 범위를 포함해서 봐 줄 필요가 없습니다.

16번째줄에서 pivot + 1 해준 것 처럼

14번째줄에서 pivot - 1 하면 됩니다.

santoo 2년 전 1

@fbfbf1 범위에서 딱 하나를 더 포함했다고 이렇게 시간초과가 날줄이야... 코딩도 아주 정확하게 해야하는군요 ... ㅎㅎㅎ 너무 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[swift] - 1920 수 찾기 문제 이분탐색 관련 시간초과

santoo 2년 전 0

fbfbf1 2년 전 0

santoo 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말