[백준] Swift 1300 k번째 수 BS(Bineary Search)

문제 :

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

1300번: K번째 수

 

풀이 :

문제를 직접 풀진 못했지만, 신기한 풀이가 있어서 기록을 남겨보려구 한다.

문제는 2차원 N*N 배열 값을 1차원 N*N배열로 바꾸었을때 k번째 인덱스의 값(m)을 구하는 문제였다.

예를 들어서 N = 4 배열이 있을때,

이를 1차원 배열로 늘여보면

이렇게 될 것이고 그러므로 이를 이분 탐색으로 접근 할 수 있는 것이다.

사실 선형 탐색으로 찾으려 했지만 N(100,000) X N(100,000) 은 백억이므로 시간초과가 나게 된다. 그래서 이분탐색으로 풀어야 한다.

예를 들어 k가 6이고 k번째 수 4(m = 4)라고 했을때 4보다 작거나 같은수들의 개수가 곧 인덱스가 된다. 따라서 k보다 작다면 left값을 증가시켜 범위가 큰 쪽에서 검사해야 한다. 반대로 개수가 k보다 크다면 right값을 감소시켜 작은 범위쪽에서 검사해야 한다.

그렇다면 m보다 작거나 같은 수는 어떻게 구할 수 있을까 ?

https://www.acmicpc.net/board/view/14272

이 글을 참고했다.

m보다 작은 값은 m 값을 i로 나눈 값과 n중 작은 값을 채택하여 다 더하게 되면 n보다 작은 값을 찾을 수 있다 (신기 ..!)

따라서 이 값을 기준으로 이분탐색을 진행하여 푸는 것이다.

 

swift 코드 :

//
//  main.swift
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2022/03/31.
//

import Foundation
var n = Int(readLine()!)!
var k = Int(readLine()!)!

func binearySearch(_ left: Int, _ right: Int) -> Int {
    if(left > right) { return left }
    var mid = (left + right) / 2
    var cnt = 0
    
    for i in 1..<n+1 {
        if(n > mid / i) { // mid 보다 작은 수 더해줌
            cnt += mid / i
        }else {
            cnt += n
        }
    }
    if(cnt < k) {
        return binearySearch(mid+1, right)
    }else {
        return binearySearch(left, mid - 1)
    }
}

print(binearySearch(1, k))