[Swift] BOJ 1300 K번째 수

 BOJ 1300 K번째 수

 

✅ wow 생각보다 오래걸렸다.

문제보고 한 10초만에 해결하겠다 싶었는데

오래걸리 ㅁㅎㅋㄷ

메모리 초과 !

 

문제 조건을 보니까 10^9(10의 아홉제곱!) 까지 가능하다고 한다.

처음에는 그냥 배열을 N by N으로 만들어서 배열 인덱스 값의 곱을 배열 value로 저장하고 flatMap 이후에 sort해서 찾았다.

메모리 초과라니..

 

 

나동빈 책 보니까 이진탐색을 정말 잘 구현하는 개발자는 10프로 정도밖에 안된다는데, 나도 90프로에 속하나보다 ㅎㅎ

이게 개념은 쉬운데, 문제 해결을 위해 적용하는게 어렵더라.

 

✅ 알고리즘 접근법.

이 문제는 알고리즘 접근법이 생각보다 어려웠다.

나동빈 책 이분탐색 부분을 보면 파라메트릭 서치라는 개념이 있는데, 그 개념을 사용해서 풀어야 했다.

이건 추후에 이분 탐색 자료구조 정리하면서 함께 포스팅 할 예정 !

 

target은 크기 순으로 sort했을 때의 몇번째에 위치했는지 찾는 코드인데, 쉽게 생각하자면 target은 이분탐색 알고리즘을 통해서 접근할 수 있다.

 

count의 값을 잘 생각해보자.

배열의 인덱스는 1부터 시작한다고 했으므로 각 배열에 들어가는 값들은 

🟠 [3X3]

1 2 3

2 4 6

3 6 9

위와 같이 값이 들어가게 된다.

 

그럼 잘 생각해보면, 구구단을 연상할 수 있다.

그리고 target보다 작은 값을 찾는다고 가정하면 결국은 mid / i가 각 row의 mid보다 작은 값이 된다.

각 row에서 더 작은 값을 count로 저장하고, 그 값을 기준으로 이분 탐색을 수행하여 mid값을 갱신한다.

 

count가 더 크다는 말은 내가 찾아야 하는 갯수보다 더 많은 count가 있다는 것이므로 high의 값을 낮추어서 더 적은 갯수를 찾게끔 조정한다.

 

👉🔥 이분 탐색에서 low와 high가 뒤집히는 부분을 집중해서 유의깊게 보고 이해하자.

이 부분만 주의하면 나는 이분탐색을 완전히 이해할 수 있다!

 

✅ 코드

 let n = Int(readLine()!)!
        let target = Int(readLine()!)!
        
        // 각 row(구구단으로 치자면 단)에서 어떤 수보다 작은 값의 갯수를 찾는다.
        
        // 1 ~ n단(row) 사이에서 정해지니까
        var low = 1
        var high = target
        
        while low < high {
            
            let mid = (low + high) / 2 // mid값 세팅
            var count = 0
            
            for i in 1...n { // 각 row를 반복하면서
                count += min(mid / i, n)
                if count > target { break } // 조금이라도 시간을 줄여보려고 
            }
            
            // count가 더 크다는 의미는 mid보다 작은 수가 target의 개수보다 많다는 뜻이므로 mid값을 줄여야 한다.
            if target <= count {
                high = mid
            } else {
                low = mid + 1
            }
        }
        
        print(low)