[BaekJoon] 1300번 k번째 수 (Java) 문제 풀이 [Gold 2]

문제

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

1300번: K번째 수

 

어떻게 풀 것인가?

문제 처음에 주어지는 수를 보면 시간복잡도의 의해서 브루트포스 알고리즘으로는 접근이 불가하다.

즉 log(N)의 시간복잡도를 가진 이분탐색을 이용한 문제이다.

이차원 배열을 일차원 배열로의 변환과 큰 수 처리가 관건인 문제였다.

 

예를 들어 4 X 4 2차원 배열에서 1차원 배열로 바꾸게 된다면 B[11] = 8이 된다.

 

문제에서는 1차원 배열을 오름차순으로 정렬하여 사용한다. 그렇다면 B[k] = A 의 의미는 "A보다 작거나 같은 원소의 개수가 최소 K개라는 의미이다. 

 

이 문제에서 찾고자하느 것은 B[k] = A에서 K인데스의 원소 값 A를 찾는 것이다. 그렇다면, A의 값을 조정해나가면서 X보다 적가나 같은 원소의 갯수가 k값이랑 일치하면 된다. <- 이 부분이 이분 탐색이다.

 

이에 long타입 사용과, 이차원 배열의 성질을 이용하여, calc함수를 이용하여 계산하였다.

 

풀면서 놓쳤던점

이분 탐색의 로직에 대한 이해보다는 이차원 배열과 큰 수 처리가 많이 어려웠다.

이 문제를 통해 얻어갈 것

이분탐색의 활용 문제

내 코드 

package baekjoon2.BJ_1300;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

// 백준알고리즘 1300번 k번째 수

public class Main {
    static long N;
    static long k;

    public static long calc(long x) {
        long ret = 0;
        for (int i = 1; i <= N; i++)
            ret += Math.min(N, x / i);
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        long left = 0, right = N * N;
        while (left <= right) {
            long mid = (left + right) >> 1;
            if (calc(mid) >= k) right = mid - 1;
            else left = mid + 1;
        }
        System.out.println(right + 1);
    }
}

 

참고

https://st-lab.tistory.com/281

[백준] 1300번 : K번째 수 - JAVA [자바]