[BOJ 1300] K번째 수 - Java

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

---

문제 설명

세준이는 크기가 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]를 출력한다.

문제 풀이

해당 문제를 처음 보고 든 생각은 n의 값이 너무 크기 때문에 직접 정렬을 하는 방식을 이용할 수 없을 것 같다라는 생각이 들었습니다. 정렬을 한다면 메모리와 시간적으로 모두 초과가 날 것이라 생각했습니다.

그러면 정렬을 수행하지 않고 문제를 풀어야 합니다. 사실 이 문제에서 제시한 조건에 따르면 값은 정렬되어 있습니다. 어떻게 정렬되어 있는지 상상이 가능합니다. 3x3이라면 1, 2, 2, 3, 3, 4, 6, 6, 9 이런 식으로 정렬될 것이 눈에 보입니다. 그리고 시간복잡도가 O(logN)이 나와야 합니다. 그렇다면 생각해볼 수 있는게 이분탐색을 이용하는 것입니다.

 

저희가 구해야 할 것이 B[k] = x 이 질문에 대한 답입니다. 이거를 거꾸로 생각해보면 x보다 작거나 같은 값이 k개 있다는 말과 같습니다. 어떻게 그렇게 될까요? B가 오름차순으로 정렬되어 있기 때문입니다. 그럼 이를 이용해서 이분탐색을 생가개보면 거꾸로 'x에 도달했을 때 x보다 작거나 같은 수의 개수가 k개면 내가 찾는 x가 맞구나' 라고 생각할 수 있습니다.

 

그럼 이제 생각해봐야 할 것은 'x보다 작거나 같은 수의 개수를 어떻게 찾을 수 있을까?' 인데요. 그냥 완탐으로 생각하면 시간복잡도가 O(NxN)가 되겠죠? 모든 수를 다 돌아보면서 갯수를 세어야 하니까요. 하지만 여기서 주어진 수들은 i x j 라는 패턴을 가집니다. 첫번째 행에선 1 x 1, 1 x 2, 1 x 3 두 번째 행에선 2 x 1, 2 x 2, 2 x 3 요렇게 나오죠. 요 값들은 구구단 1단, 2단의 일부다 라고 생각할 수 있습니다. 그리고 각 단들은 누적합처럼 2, 4, 6 이런식으로 더해지니까 2단에서 8보다 작거나 같은 값을 구하려면 2가 몇번 더해졌는가를 생각하면 됩니다. 이를 수식으로 표현하면 8 / 2 = 4가 되겠죠? 3 x 3에서 8보다 작은 값을 찾기 위해선 각 단에서 8을 나눈 몫을 더하면 된다는 얘기입니다.

 

하지만 조금 이상한 점이 있는데요. 8 / 1 = 8인데 실제 3x3 배열에는 1단이 3까지 밖에 존재하지 않죠? 그렇기 때문에 min(3, 8 / 1) 요렇게 n보다 커진다면 n을 더하는 로직을 이용해야 합니다.

 

이제 이분 탐색을 이용해서 어떻게 값을 도출할지를 생각해보면 최소 값부터 최대 값까지 이분탐색을 진행하겠죠. 여기서 최대 값은 뭐가 될까요?? k입니다. 물론 n * n을 이용해도 좋지만 x <= k 라는 특성을 이용해서 k로 설정을 해줄 수 있습니다.

 

마지막으로 이분탐색 과정에 대해서 설명해보겠습니다. x보다 작거나 같은 수의 개수가 k보다 더 작다면 x의 값이 너무 작다는 의미이고 x보다 작거나 같은 수의 개수가 k보다 더 크다면 x의 값이 너무 크다는 의미입니다. 이 구현에서는 upper bound나 lower bound 같은 접근이 필요한데요. 그 이유는 실제로 존재하지 않는 값임에도 탐색해야하는 경우가 존재하기 때문입니다.

이런 이유로 Lower Bound를 이용해서 이분 탐색을 구현해보겠습니다.

---

구현 코드

import java.io.*;

public class Main {
    private static int n, k;
    
    public static void main(String args[]) throws IOException {
        initialize(); // 입력 받기.
        System.out.println(getKNumber());
    }
    
    private static void initialize() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
    }
    
    private static long getKNumber() {
        long start = 1;
        long end = k;
        while (start < end) {
            long mid = (start + end) / 2;
            long numberLowerThanMid = countLowerThan(mid);
            
            if (numberLowerThanMid < k) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return end;
    }
    
    private static long countLowerThan(long mid) {
        long cnt = 0;
        for (int i = 1; i <= n; i++) {
            cnt += (Math.min(n, mid / i));
        }
        return cnt;
    }
}

 

Reference

https://st-lab.tistory.com/281#:~:text=%EC%A0%95%EB%A6%AC%ED%95%98%EC%9E%90%EB%A9%B4%20B%5BK%5D%20%3D,%EA%B2%83%EC%9D%84%20%ED%99%95%EC%9D%B8%20%ED%95%A0%20%EC%88%98%20%EC%9E%88%EB%8B%A4.

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

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=occidere&logNo=221045300639 

Upper Bound(상계), Lower Bound(하계)