NN단표

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. O(N^2) 완전탐색을 통해 문제를 해결하게 되면 100,000 * 100,000이므로 시간안에 문제를 해결할 수 없음
2. 우리가 알 수 있는 수는 1 ~ N * N 범위의 수이고, 해당 범위의 수가 몇 번째 수인지 O(N)의 시간복잡도로 알아낼 수 있음
3. NN단표에서 1부터 N까지 중, 1 * N이 현재 수보다 작게 되면 현재의 단계에서는 현재 숫자보다 작은 숫자가 N개가 있다는 것을 알 수 있고,
4. 현재 숫자가 현재 단계로 나누어 떨어지게 된다면 그 몫에서 자기 자신을 제외하게 되면 현재 숫자보다 작은 숫자의 개수를 알 수 있고,
5. 나누어 떨어지지 않는다면, 그 몫이 현재 숫자보다 작은 숫자의 개수임을 알 수 있음
6. 위 3 ~ 5 과정의 개수를 모두 더해 + 1을 반환하게 되면 O(N)만에 1 ~ N * N숫자의 범위에 해당하는 각각의 숫자가 몇 번째 숫자인지 알 수 있음
7. 이를 통해 현재 찾고자 하는 숫자의 위치 K와 비교하여 이진탐색을 통해 O(N log N)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - NN단표

//MARK: - Framework
import Foundation

//MARK: - Function
func getOrder(_ N: Int, _ number: Int64) -> Int64 {
    var result: Int64 = 0
    for i in 1...N {
        if i * N < number {
            result += Int64(N)
        } else {
            result += number % Int64(i) == 0 ? number / Int64(i) - 1 : number / Int64(i)
        }
    }
    result += 1
    
    return result
}

func binarySearch(_ N: Int, _ start: Int64, _ end: Int64, _ K: Int64) -> Int64 {
    if start + 1 >= end {
        return start
    }
    
    let mid: Int64 = (start + end) / 2
    return getOrder(N, mid) <= K ? binarySearch(N, mid, end, K) : binarySearch(N, start, mid, K)
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let K: Int64 = Int64(readLine() ?? "0") else { return }
    
    //MARK: - Process
    let result: Int64 = binarySearch(N, 1, Int64(N * N + 1), K)
    
    //MARK: - Output
    print(result)
    
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.