[코딩테스트] - ⚔ Sort 마스터 배지훈

20551 백준 Sort 마스터

난이도

실버 4

유형

Binary Search

소요시간

1시간 이상...

회고

처음에 기본 구현 method로 풀었다가 시간초과가 떠서 사용할 수 있는 알고리즘 찾아보았다. 주어진 수의 범위가 10의 5승 등으로 커서 Binary Search 적용하여 풀었다.

Binary Search 적용 중 중복 value를 고려하지 않아서, 가장 빠른 index가 아닌 값을 return하여 오답 발생하였다.

처음 시도

func binarySearch(arr: [Int], target: Int) -> Int {
        var left = 0
        var right = arr.count - 1
        var result = -1

        while left <= right {
            let mid = (left + right) / 2

            if arr[mid] == target {
                return mid // 💥 가장 빠른 index가 아닌 index return
            } else if arr[mid] > target {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return result
    }
}

최종 코드

func sortMaster() {

    let line = readLine()!.split(separator: " ").compactMap { Int(String($0)) }
    let (n, m) = (line[0], line[1])

    var A = Array(repeating: 0, count: n)
    (0..<n).forEach { i in
        let v = Int(readLine()!)!
        A[i] = v
    }
    let B = A.sorted()

    var D = Array(repeating: 0, count: m)
    (0..<m).forEach { i in
        let v = Int(readLine()!)!
        D[i] = v
    }

    (0..<D.count).forEach { i in
        print(binarySearch(arr: B, target: D[i]))
    }

    func binarySearch(arr: [Int], target: Int) -> Int {
        var left = 0
        var right = arr.count - 1
        var result = -1

        while left <= right {
            let mid = (left + right) / 2

            if arr[mid] >= target {
                if arr[mid] == target {
                    result = mid
                }
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return result
    }
}