[BOJ] 백준 1300번 : K번째 수(JAVA)

문제의 링크 : https://www.acmicpc.net/problem/1300

1300번: K번째 수

문제

세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.

배열 A와 B의 인덱스는 1부터 시작한다.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다.

 

풀이

이분탐색을 이용하여 풀 수 있는 문제였습니다. 처음에는 2차원 배열에 i * j에 해당하는 값을 모두 넣어주고, 이것을 1차원 배열에 옮긴 뒤, 오름차순 정렬을 하려고 했습니다. 하지만, N은 최대 10^5였고, 이것을 1차원 배열로 옮기면 사이즈가 10억이나 되기때문에 메모리 초과 및 시간 초과를 피할 수가 없습니다.

이런 저런 고민을 하던 중, 2차원 배열을 한 번에 만들어 놓고 접근하는 것이 아니라, 임의의 수는 몇 번째인지부터 접근해 보기로 하였습니다.

예를 들어, N이 3일 경우 2차원 배열은 아래와 같을 것입니다.

여기서 예를 들어, 4는 오름차순으로 정렬하였을 때 몇 번째 오는지 생각해 보았습니다.

첫 번째 줄은 모두 4 이하고, 두 번째 줄은 4 이하가 2개가 있고, 세 번째 줄은 4 이하가 1개가 있었습니다. 그래서 위를 계산한 개수는 총 6개고, 실제로 4는 6번째에 오는 수 입니다.

이 부분에서, 저는 아래와 같은 중요한 식을 도출해낼 수 있었습니다.

 

cnt = min(mid / i, N)   -> mid는 임의의 수, i는 i번째 줄을 의미.

 

즉, 이 식을 세운 순간부터 우리가 할 일은 1가지로 줄어들게 됩니다.

left = 1, right = K로 두고, left <= right일 때까지 while문을 진행하면서 위 식에 따라서 cnt를 계산한 후, cnt와 K를 비교하면서 left 혹은 right를 초기화하는 것입니다.

 

예제

N이 3, K가 7일 경우

left = 1, right = 7로 초기화를 하고 시작합니다.

mid = (left + right) / 2 = 4이고, 첫 번째줄부터 세 번째줄까지 위 식을 대입하겠습니다.

min(4 / 1, 3) = 3

min(4 / 2, 3) = 2

min(4 / 3, 3) = 1

총 cnt = 6이 됩니다. 그리고 cnt < K이므로 left = mid + 1 = 5로 초기화할 수 있습니다.

 

mid = (left + right) / 2 = 6이고, 첫 번째줄부터 세 번째줄까지 위 식을 대입하면,

min(6 / 1, 3) = 3

min(6 / 2, 3) = 3

min(6 / 3, 3) = 2

총 cnt = 8이 됩니다. 그리고 cnt >= K 이므로 right = mid - 1 =  5로 초기화할 수 있습니다. 그리고 cnt >= K인 경우에는 ans = mid로 초기화해 주면 됩니다.

이후에 left = right가 되므로 반복문은 종료하고, ans는 6이라는 사실을 알 수 있습니다.

 

아래는 위 로직을 구현한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
 
        long left = 1, right = K;
        long ans = 0;
        
        // 이분 탐색 수행
        while (left <= right) {
            long mid = (left + right) / 2; // 임의의 수 지정
            long cnt = 0;
            
            // mid보다 작거나 같은 수는 몇 개인지 계산.
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid / i, N);
            }
 
            if (cnt < K) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.