Q6_1300(K번째 수)

📌 문제

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

입력)
첫째 줄에 배열의 크기 N이 주어진다.
N은 105보다 작거나 같은 자연수이다.
둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

출력)
B[k]를 출력한다.
시간 제한 : 2초
메모리 제한 : 128MB

📌 문제 분석❗️

❗️배열 B는 N * N 행렬을 한 줄로 세워 오름차순으로 정렬한 배열이다.

각 행렬 구간은 i x j의 값을 가진다. 해당 행렬을 한 줄로 나열한 뒤 오름차순으로 정렬한 것이 배열 B이다.

 

❗️Brute-Force Algorithm으로는 풀 수 없다.

배열의 크기 N은 최대 10만 개이다. 100,000 개 * 100,000 개 > 2초이므로 행렬을 만들지 않고 나열한 배열 b[k]의 값을 구해야된다. 따라서 Brute-Force 알고리즘은 사용할 수 없다.

 

❗️B[k] = x 라는 의미

B 행렬은 오름차순으로 정렬된다. k번 인덱스의 값이 x란 말은 결국 x보다 같거나 작은 수가 k개 있다는 말과 동일하다.

N = 4, B[10]의 값을 구한다고 가정해보자.

B[10]의 값은 6이다. 4 x 4 행렬에서 6보다 작거나 같은 경우 또한 10개인 것을 확인할 수 있다.

 

❗️행렬을 자세히 보면 구구단 모양이다.

N x N 행렬을 자세히 보면 길이가 N인 구구단 모양을 하고 있는 것을 알 수 있다.

따라서 B[10] = 6이면 해당 구구단에서 6보다 작거나 같은 수를 찾으면 된다. 어떻게 구할 수 있을까? 바로 x를 단 수로 나누면 된다.

[x 값 : 6]

1단 : {1, 2, 3, 4, 5, 6, 7, 8, 9}  ->  6/1 = 6

2단 : {2, 4, 6, 8, 10, 12, 14, 16, 18}  ->  6/2 = 3

3단 : {3, 6, 9, 12, 15, 18, 21, 24, 27}  ->  6/3 = 2

4단 : {4, 8, 12, 16, 20, 24, 28, 32, 36}  ->  6/4 = 1

5단 : {5, 10, 15, 20, 25, 30, 35, 40, 45}  ->  6/5 = 1

6단 : {6, 12, 18, 24, 30, 36, 42, 48, 54}  ->  6/6 = 1

7단 : {7, 14 ,21 ,28, 35, 42, 49, 56, 63}  ->  6/7 = 0

8단 : {8, 16, 24, 32, 40, 48, 56, 64, 72}  ->  6/8 = 0

9단 : {9, 18, 27, 36, 45, 54, 63, 72, 81}  ->  6/9 = 0

 

그런데 N 값이 만약 4라면 행렬의 크기가 최대 4칸 밖에 안된다. 따라서 단에서의 최대 카운트 개수는 N을 넘어선 안된다.

 

❗️x의 값은 k보다 작거나 같다.

문제에서 찾으려고 하는 값은 바로 x 값이다.

k의 최대 값은 N^2이고 x의 최대 값도 N^2이다. 따라서 x <= k를 만족한다. 이를 이용해 start와 end를 주어 이분 탐색을 진행할 수 있다.

 

📌 진행

❗️start = 1, end = k

int N = readInt();
int k = readInt();
int start = 1;
int end = k;

while (start < end) {
    int count = 0;
    int mid = (start + end) / 2;

앞서 설명한 것과 같이 x의 범위는 k보다 작거나 같음을 만족한다. 따라서 end 값을 k로 설정할 수 있다. 해당 값을 통해 이분탐색을 진행한다.

 

❗️count는 N을 넘을 수 없다.

for (int i = 1; i <= N; i++) {
    count += Math.min(mid / i, N);
}

mid / i (단에서의 숫자 개수)가 행렬의 바운더리 N보다 클 수 없다. 때문에 Math.min을 통해 더 작은 값을 비교하여 count에 누적해준다.

 

❗️이분 탐색 범위 조정

// 이분 탐색의 왼쪽 영역을 탐색한다.
if (k <= count) {
    end = mid;
} else { // 이분 탐색의 오른쪽 영역을 탐색한다.
    start = mid + 1;
}

• k가 mid보다 작거나 같다면,
  예상보다 더 많이 카운트됨 :  예상하는 x를 줄여야 한다.
  → end = mid를 통해 왼쪽 영역을 탐색한다.
• k가 mid보다 크다면,
  예상보다 더 적게 카운트됨 : 예상하는 x를 높여야 한다.
  → start = mid + 1를 통해 오른쪽 영역을 탐색한다.

 

❗️이분 탐색을 마쳤다면 최종적으로 start를 출력해준다.

        System.out.println(start);

최종적으로 start에 담긴 값은 카운트 미달 바로 앞의 카운트를 만족하는 값을 가리키므로 정답 x가 된다. 

 

📌 전체 코드

package level22_이분탐색_.Q6_1300;

import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException{
        int N = readInt();
        int k = readInt();
        int start = 1;
        int end = k;
        while (start < end) {
            int count = 0;
            int mid = (start + end) / 2;
            for (int i = 1; i <= N; i++) {
                count += Math.min(mid / i, N);
            }
            // 이분 탐색의 왼쪽 영역을 탐색한다.
            if (k <= count) {
                end = mid;
            } else { // 이분 탐색의 오른쪽 영역을 탐색한다.
                start  = mid + 1;
            }
        }
        System.out.println(start);
    }

    private static int readInt() throws IOException {
        boolean isNegative = false;
        int value = 0;

        while (true) {
            int input = System.in.read();
            if (input == ' ' || input == '\n') {
                return isNegative ? -1 * value : value;
            } else if (input == '-') isNegative = true;
            else value = value * 10 + (input - 48);
        }
    }
}

 

📌 참조

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

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