[백준] (Swift) 10816번 - 숫자카드2 (이분탐색, upper bound, lower bound)

이분탐색을 진행할 때는 존재여부를 확인할때는 괜찮지만, 개수를 세어야할 경우에는 탐색하고자하는 배열 내부에 중복값이 있으면 안된다. 그럴때를 대비해서 upper bounds 방법과 lower bounds 방법을 잘 알아두어야 문제를 맞출 수 있을 것 같다.

 

⚫️ 문제

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

 

⚫️ 나의 풀이

아 그리고 문제 풀고 발견한건데, dictionary를 사용하면 진짜 개 간단하게 풀 수 있다 .ㅋㅋㅋㅋㅋㅋㅋ dictionary에서는 값에 접근하고, count해주는 시간복잡도가 O(1)이기 때문
contain메서드는 dictionary에서 O(N)이긴 함

 

우선, 백준에서 이분탐색으로 분류가 되어있는 문제다. 

◾️ 처음 생각한 풀이

당연히 처음에는 이분탐색으로 풀어야겠다고 생각했다. 

• 입력받는 cards를 sort()로 정렬해주고
• 숫자 m개를 for문을 돌려 -> O(N)
• 이분탐색을 진행하고, 내부에 값이 있다면 -> O(logN)
• filter로 지금 보고있는 범위 내부에서 같은 수 몇개인지 판단 -> O(N)

이렇게 생각했다. 근데,,,, 생각해보니까, 중간값을 기준으로 계속 범위를 나누는 것이기 때문에 filter로 start ~ end 까지 내부에서 count를 해주면 놓치는 수가 분명히 있을 것이라고 생각되었다.

이 경우에 만약 타겟이 4라 치고, start~end까지 내부에서 4를 찾으면, 2개이다. 우리가 원하는 답은 3이 아닌가 ? 그럼 이렇게 filter를 이용하는 방법은 안될 것 같았다.

◾️ 두번째로 생각한 풀이

똑같이 이분탐색을 진행하고, 출력된 위치의 양옆에 동일한 값이 몇개가 있는지 판단하는 방법이었다.

• 입력받는 cards를 sort()로 정렬해주고
• 숫자 m개를 for문을 돌려 -> O(N)
• 이분탐색을 진행하고, 내부에 값이 있다면 해당 mid값출력-> O(logN)
• mid 양옆 기준으로 mid와 같은 값을 갖고있는지 count -> O(N)

이렇게 하게 된다. 조건을 살펴보면, N은 50만이 최대, M도 50만이 최대인데, 그렇게 되면 최악의 경우 2억회가 넘는 loop를 돌아야한다. 시간초과가 나는게 당연하지 않을까?

◾️ 인터넷 참고 -> upper / lower 범위를 구할 수 있다.

인터넷을 보니, 이분탐색과 똑같은 방식으로 돌아가지만 '범위'를 구하는 것을 목적으로 함수를 작성할 수 있었다.

- lower bound: 원하는 값 k 이상이 나오는 위치를 찾음
- upper bound: 원하는 값 k 초과가 나오는 위치를 찾음

이렇게 두개의 함수로 나눠서 구현하고, lower bound의 출력값은 타겟값 이상!이 나오는 위치 인덱스를 출력하고, upper bound는 타겟값 초과가 나오는 순간의 인덱스 위치를 찾아 출력하는 것이다. 

이렇게 구하게 되면, 이분탐색을 두번 사용해서 upper값과 lower값을 찾아내고 (2 * log N), upper - lower 값을 해주면 내가원하는 타겟값의 count 횟수가 출력된다. 

◾️ 틀렸습니다

위처럼 풀었는데 틀렸다. 왜 틀렸을까?
내가 구한 upper 값과 lower 값을 모두 출력해서 찍어보니 문제가 있었다. 당장 백준 예제에 나와있는 사례로 보면,

타겟값이 만약 cards 내부의 최대값이라면, cards내부에서 인덱스 가장 마지막 값을 갖는데, 그럼 우리는 up - low 값을 출력할때 원하는 3이 아니라, 2라는 출력값을 갖게 된다.

그래서 나는, cards를 입력받고, 맨 마지막 에 임의로 제일큰수 + 1해준 값(여기서는 11)을 cards에 추가로 넣어주었다.

아 잠깐, 그럼 또 target값이 11이 된다면 답은0인데 1을 출력하게 되지 않냐구? 
아니다. 우리가 지금 짜놓은 구조로 보면, 이상일 경우에 low를 설정해주고, 초과가 날경우 up을 설정해주지만 위에서 보다시피 up값이 최대값이라면, 그냥 cards의 마지막 인덱스값을 갖는다.

현재 임의로 넣어준 11로 보면, up과 low는 결국 같은 값을 갖게 될 것이다. 그래서 정답은 결국 0이 출력되게 된다! 

 

⚫️ 정답 코드

import Foundation

let n = Int(readLine()!)!
var cards = readLine()!.split(separator: " ").map{ Int($0)! }.sorted(by: <)
cards.append(cards[cards.count - 1] + 1)
let m = Int(readLine()!)!
let nums = readLine()!.split(separator: " ").map{ Int($0)! }

func lowerBound(arr: [Int], start: Int, end: Int, target: Int) -> Int {
    var start = start
    var end = end

    while end > start {
        let mid = start + ((end - start) / 2)

        if arr[mid] >= target {
            end = mid
        } else {
            start = mid + 1
        }
    }

    return start
}

func upperBound(arr: [Int], start: Int, end: Int, target: Int) -> Int {
    var start = start
    var end = end

    while end > start {
        let mid = start + ((end - start) / 2)

        if arr[mid] > target {
            end = mid
        } else {
            start = mid + 1
        }
    }

    return end
}

for i in 0..<m {
    let target = nums[i]
    let up = upperBound(arr: cards, start: 0, end: n, target: target)
    let low = lowerBound(arr: cards, start: 0, end: n, target: target)
    print("\(up - low)", terminator: " ")
}