[필수 문제] NN단표

1. 문제

알랩이는 구구단표처럼 NN단표를 만들었다고 한다.

 

NN단표는 2차원 배열의 모양으로 곱셈 1단부터 N단까지의 값들을 적어놓은 형태이다.

 

NN단표의 배열을 A라고 했을 때, 배열의 들어가는 수 A[i][j]=i*j이다.(즉, 4행 7열에는 28, 7행 5열에는 35가 들어가 있다.)

 

알랩이는 N단까지 나온 숫자들 중에서 K번째로 작은 수를 찾고 싶어한다.

 

이때, 중복되는 여러 수들을 고려한다. 즉 N*N개의 모든 수들 중에서 K번째 수를 구하는 것이다.  

---

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄에 K가 주어진다. K는 N*N보다 작거나 같은 자연수이다.  

출력

K번째 원소를 출력한다.

예제 입력

3
7

예제 출력

6

 

 

 

2. 풀이

NN단표는 N의 조건이 '100,000보다 작거나 같은 자연수'라는 점에서 까다로운 문제다. 일반적인 경우라면, 주어진 n에 따라 2차원 배열을 만들고, 만든 배열을 1차원 배열에 정렬하여 저장한 뒤, 1차원 배열에서의 k번째의 수를 출력해주면 된다. 하지만 N이 100,000일 경우 어마어마한 계산량이 요구된다. 따라서 이 문제는 배열로 접근해서는 안된다

 

1차원 배열에 정렬하여 문제를 해결하는 경우의 시간복잡도는 다음과 같다.

• N x N개의 숫자를 1차원 배열에 넣는데 O(n^2)
• 1차원 배열을 정렬하는데 O(n^2 log n^2)
• 즉, O(n^2) + O(n^2 log n^2)의 시간이 소요

 

따라서 이 문제를 해결하기 위한 가장 핵심적인 아이디어로는,  '특정 숫자가 몇 번째에 있는지' 이다. 이 뜻은 예제를 통해 이해할 수 있다.

n = 4, k = 8
1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

1

2

2

3

3

4

4

4

6

6

8

8

9

12

12

16

위의 예제의 답은 k가 8이기에 4가 된다. 반대로 특정 숫자 - 4를 알 때, 4의 인덱스 값을 찾는다고 가정해본다. 4의 값을 가진 인덱스로는 6, 7, 8번 인덱스이 있음을 알 수 있다. 그리고 k의 값이 8이므로 8번째에 있는 4의 값이 정답이 된다.

 

그렇다면 4의 값을 가진 인덱스가 6, 7, 8번에 있는지 어떻게 알 수 있는지에 대해 생각해보아야한다. 이 문제는 비교적으로 단순하게 해결할 수 있다. 4보다 작거나 같은 값을 가진 수의 개수와 4보다 작은 값을 가진 수의 개수를 찾으면 된다.

• 4보다 작거나 같은 값을 가진 수의 개수 :  1) 1개 + 2) 2개 + 3) 2개 + 4) 3개 = 8개
• 4보다 작은 값을 가진 수의 개수 : 1) 1개 + 2) 2개 + 3) 2개 = 6개
• 즉, 4는 6 ~ 8번 인덱스에 존재함을 확인

 

여기까지 이해를 했다면, 다음으로는 정렬된 배열을 만들지 않고도 각 요소의 개수를 알아내는 방법을 생각해야한다.

 

다음의 예제에서 12보다 작은 값을 구한다고 가정해본다.

• 1행의 마지막 요소는 12보다 작기 때문에 1행의 모든 요소는 12보다 작다. 따라서 총 4개가 있다.
• 2행의 마지막 요소는 12보다 작기 때문에 2행의 모든 요소는 12보다 작다. 따라서 총 4개가 있다.
• 3행은 12 / 3(행) - 1 개가 있다.
• 4행은 12 / 4(행) - 1 개가 있다.
• 총 4 + 4 + 3 + 2 = 13개가 있다.

 

n = 4, k = 8
1	2	3	4
2	4	6	8
3	6	9	12
4	8	12	16

 

위의 모든 과정을 이용하면 다음과 같이 코드를 구성할 수 있다.

• 가장 첫 번째 요소와 가장 마지막 요소 사이의 모든 수의 중간값을 구한다.
• 중간값의 위치(인덱스)를 구한다.
• 중간값의 위치가 k보다 작거나 같을 경우와 클 경우를 나누어 k 번째 수를 구한다.

 

※ 단, int 자료형을 사용하면 안된다는 점을 주의해야한다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static long n;
    private static long k;

    public static void main(String[] args) throws IOException {

        n = Long.parseLong(br.readLine());
        k = Long.parseLong(br.readLine());

        /*
        1 2 3 4
        2 4 6 8
        3 6 9 12
        4 8 12 16

        1 2 2 3 3 4 4 4 6 6 8 8 9 12 12 16
         */

        long first = 1; // NN단표 특성상 배열의 첫 번째 요소는 항상 1이 된다.
        long last = n*n + 1; // 마지막 요소를 포함하기 위해 + 1을 해준다.

        while(first + 1 < last) {
            long mid = (first + last) / 2; // 중간값
            long order = getOrder(mid); // 중간값의 위치

            if(order <= k) first = mid; // 중간값의 위치가 k 번째보다 작거나 같을 때
            else last = mid; // 중간값의 위치가 k 번째보다 클 때
        }

        bw.write(first + "");
        br.close();
        bw.flush();
        bw.close();
    }

    private static long getOrder(long num) {
        /*
        1 2 3 4
        2 4 6 8
        3 6 9 12
        4 8 12 16

        x = 12일 경우
        1 2 3 4   --- 4개 : 4개
        2 4 6 8   --- 4개 : 4개
        3 6 9 12  --- 3개 : 12 / 3(행) - 1 개
        4 8 12 16 --- 2개 : 12 / 4(행) - 1 개
         */
        long result = 0;
        for(int i = 1; i <= n; i++) {
            if(i * n < num) result += n;
            else {
                if(num % i == 0) result += (num / i) - 1;
                else result += num / i;
            }
        }
        return result + 1;
    }
}