[백준] (Swift) 1300번 - K번째 수 (골드2) 이분탐색 범위설정.. 어캄?

무려 골드2라서 엄청 겁먹었던 문제...
엄청 어려웠다기보다는, 문제를 읽고 그것을 해석하는 과정까지가 어려웠다. 끄것만 생각하면 바로 풀리는 문제?
하지만, 이 문제를 풀면서 궁금한점이 생겼다. 결과값을 왜 다 찍어봐도 모르겠지?

 

⚫️ 문제

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

1300번: K번째 수

 

⚫️ 나의 풀이

처음에 보자마자 엥 이게 왜 골드? 싶었다. 그러는 순간 조건을 봤는데 최악의 경우가 100억ㅇ이 나오는게 아닌가!! 그렇다면... O(N^2) 완탐으로는 풀순 없다는 뜻인데!!

처음 생각한 풀이는, i*j를 모두 계산한 list를 만들어주고 인덱스로 접근하는 것 ㅋㅋㅋㅋㅋㅋㅋㅋ 

그렇다면, 배열 B의 최대 길이가 100억이 나온다. 모두 구해서 배열 B를 만드는것은... 무조건 불가능하다. 그렇다면? 시간복잡도를 줄일 수 있는 이분탐색을 이용해서 B[K]를 찾아주어야 한다는 말이다! 도대체 무슨 어떻게 이걸 어캄? 어캄 어캄어케구함????? 

도저히 감이 오지 않았다. ... 그렇게 머리를 굴리다가 생각해낸건...

찾아낸 규칙중 하나는,,, 이렇게 입력된 2차원 배열 A의 값들은 i*j를 담고 있으므로, 빨간선을 기준으로 결과값이 동일하게 나온다는 것이다... 이것을 좀 이용해서 탐색하는 범위를 절반으로 줄이면 안되려나?? 싶었으나.... 절반으로 탐색범위를 줄여도 50억이다.ㅋㅋㅋㅋㅋㅋ 이것도 짤!

ㅇ으아아아아아 그럼 어케한다는거야 어케한다는거야 넘어려워 .... 그러던 와중 이분탐색의 대상을 먼저 찾아봐야겠다고 생각을 정리했다. 그렇게 하고 left와 right를 설정해보고, mid를 설정해보았다. 바로 이전 포스팅에서 (programmers 징검다리) mid의 의미를 기억하며 대상을 찾자고 다짐했다. 그렇게 생각해낸게 바로 이것!

우선, 결과값인 숫자가 나오기 위해서는, 최소값은 1 일것이고, 최대값은 주어진 N의 제곱인 9일 것이다. (백준 예제 1 기준) 왜냐면??? 우리는 B배열 내부에 i*j의 값만 들어갈 수 있기 때문에 최대로 N*N이라는 수가 들어간다. 그래서 left를1 right를 9로 설정해주게 된다면, mid가 5가 나온다. 문제의 출력 조건이 '오름차순 정렬햇을때 B[k]'를 구하라는 것이다. 즉, K번째의 수가 뭐냐? 라는 뜻인데, 여기서 이 K번쨰에 있는 수가 mid가 된다는 것이다. 

(여기 생각해내는게 좀 어려웠음 ㅠㅠ ) 그렇다면 그렇다면! k번째수가 5이기 위해서는, 5앞에 5보다 작거나 같은수가 K-1개 있어야한다. 만약 5앞에 K-1보다 많은 수가 있다면, 현재 5는 K번째보다 훨씬 뒤에 있는 수라는 뜻이기 때문에 앞에 범위를 줄여줘야한다. 그럼 right를 mid - 1로 만들어주면 되겠지? 반대로 만약 5앞에 k-1만큼의 수 혹은 그거보다 작은수만큼 있따면? K번째보다 앞에 있다는 뜻이기 때문에, 앞의 범위를 늘려주어야한다. 그럼 left = mid + 1로 만들어주면 된다! 

⚠️ 아니 여기서, 범위를 어케 잡느냐에 따라 결과가 다르게 나와서 미칠 지경이다.

처음에 작성한 범위는 이랬다. 근데 답이 6이 아니라 5가 나오는게 아닌가!!

// (1)번 ❌ 틀린 코드 
if minCount > k  {
    right = mid - 1
} else {
    answer = mid
    left = mid + 1
}

근데 또 아래처럼 작성하면 정답처리가 된다.

// (2)번 ✅ 정답코드
if minCount < k {
    left = mid + 1
} else {
    answer = mid
    right = mid - 1
}

 

진짜 도대체 왜 minCount >= k 일때 anwer=mid를 설정해주어야하는거지? 싶었다. 진짜 도저히 이해가 가지 않았는데,,,, 이제 ... 이해가 되어서 설명해보려고한다. (모든 블로그가 설명해주지 않아서 뽀록으로 걍 맞추는건가 싶었음 ;;)

자 예제1에서 나올 수 있는 배열 B를 보자.

이렇게, 모든 수가 다르지 않고 중복되는 수도 생긴다. 우리는 노란색 인덱스 7번에 있는 6을 찾아내고 싶은것이다. 그럼 여기서 어케 비교해서 mid가 6이 나왔는지 생각해보자. 

현재 이 상황에서 노란색 부분 6이 K = 7번 째 정답이다. 하지만, 이분탐색의 특징을 잘 기억해보면 이분탐색은 '정확한!!!!'정답을 찾지 못한다는 단점이 있다. (뭐,,, 그럼 잘 맞출 수 있도록 문제가 출제 되겠지?) 어쨌든, 위의 if 문을 보면, minCount가 7보다 크거나 같으면 answer = mid를 수행한다. minCount는 지금 mid인 수 '6'보다 작거나 같은 수 의 갯수를 count한다. 그럼?? K=8 위치에 있는 값도 6이기 때문에 같이 count 가 될 것이다. 그럼 지금 현재 minCount는 8일 것이다. 

프린트 해본 결과, minCount는 8이 나온다.

만약 여기서 조건이 (1)번 ❌ 틀린코드 범위처럼 설정이 되어있따면, 8>7 이기 때문에 answer 에 6이 저장되지 않게 된다. 그렇기 때문에 우리는 여기서 minCount >= k 인 (2)번 ✅ 정답코드 범위로 설정해주어야한다!! ! 

이렇게 이분탐색에서는 예제를 잘 보고 모든 경우의수를 판단하여 범위를 설정하고, mid값을 주는 범위를 어떻게 주어야하는지 까지도 잘 고민이 되어야 맞출수 있다. 🤔🤔🤔🤔 그렇기 때문에 이분탐색 문제는 아직 나에게 더더 어렵게 느껴진다!

🤔 그리고 또 여기서, mid보다 작은 수들의 개수는 어케 구했냐고?

이것은... 나도 잘 모르겠어서 인터넷을 참고했다 ㅠㅠ 도저히 for 문으로 완탐 돌리는것 말고는 생각이 안났다.... 근데 역시나,, 수학적으로 접근하는 노련함이 필요했다.

for i in 1..<n+1 {
    minCount += min(mid / i, n)
}

이게 무슨 의미냐??!?!?  그림으로 그려보자... (아 이런 수학적인 접근 어케 ... 구하는거야 ㅠㅠ 진짜 문제 많이 풀어보는게 답이다.. ) 

와우 ... 그냥 간단한게 i*j 를 for문을 사용하는게 아니라, 간단한 수학식으로 구할 수 있었다. 그리고 , 명확한 처릴르 위해 min 처리까지 해주는 저... 대단함...! 이렇게 i*j중 현재 mid보다 작은수가 몇갠지 구할 수 있따. 코드로 작성하면 행만큼만 반복하기 때문에 10만번 돌아갈 것이고, O(100000)이 될 것이다.

 

⚫️ 정답코드

import Foundation

let n = Int(readLine()!)!
let k = Int(readLine()!)!

private func solution() {
    var left = 0
    var right = k
    var answer = 0

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

        for i in 1..<n+1 {
            minCount += min(mid / i, n)
        }

        if minCount < k {
            left = mid + 1
        } else {
            answer = mid
            right = mid - 1
        }
    }

    print(answer)
}

solution()