K번째 수(백준 1300번)

 

문제 설명

N = 3 이고 K = 7이 주어줬을 때,

 

문제에 대한 아이디어

 

시간복잡도 생각해보기

k의 범위가 최대 10의 9승이므로 시간 복잡도가 N의 2승인 알고리즘은 사용할 수 없다. 상수시간이나 NlogN시간안에 문제를 해결해야 한다.  그때 필요한 것이 이진 탐색이다.

 

실패한 방법

처음에는 처음부터 N*N 크기의 일차원 배열을 만든 뒤, 거기에 i*j를 하나씩 넣었다. 그 뒤 sort함수를 사용하고 k 번째 수를 찾았다. 제일 보편적으로 생각할 수  있는 방법이지만 i*j의 수를 일차원배열에 집어 넣을 때 N제곱 반복문을 사용하므로 당연히 시간초과가 났다. 

 

성공한 방법

그래서 생각한 방법이 이진 탐색이다. 이 문제가 이진 탐색 분류에 있어 이진 탐색을 쉽게 생각했지만 만약 그냥 이 문제를 만났다면 이진 탐색을 생각하는 것은 매우 어려웠을 것 같다.

• 이 차원 배열의 K번째 숫자는 무조건 K 보다 작다. (start = 1, end = k)
• 중앙 값을 찾는다. ((start + end) / 2)
• 중앙 값 보다 같거나 작은 수의 갯수를 찾는다. (중요한 점)
• 만약 중앙 값보다 같거나 작은 수의 갯수가  k 보다 크면 정답 = mid로 하고 다음 탐색 범위는 end = mid -1이다
• 만약 중앙 값보다 같거나 작은 수의 갯수가  k 보다 작으면 다음 탐색은 start = mid + 1이다.
• start >= end 일 때 까지 계속한다.

중요한 점은 중앙 값 보다 같거나 작은 수의 갯수를 찾는 것이다. 

각 행의 요소 값은 첫번째 행 값의 배수이다.  또 열은 그 수가 그 행에서 몇번째 수인지를 알려준다. 즉 앞의 수가 몇개 인지를 알려준다.그러므로 중간값보다 작은 최대의 값을 찾으면 그 앞까지 몇개가 존재하는지 알 수 있다. 3번째 행을 예를 들면 첫번째 값은 3이므로 4 / 3 = 1. 즉 3 * 1이 4보다 작은 최대의 수이기 때문에 1개이다.

 

전체 코드

import java.util.*;


public class 백준_1300 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long start = 1; long end = k;
        long mid = 0;
        long count=0;
        long answer=0;
        while(start <= end){
            count=0;
            mid = (start+end)/2;
            // 중간값보다 작은 수의 갯수를 찾는 부분
            for (int i = 1; i <= n; i++) {
                count += Math.min(mid/i,n);
            }
            if(count >= k){
                answer = mid;
                end = mid -1;
            }
            else{
                start = mid+1;
            }
        }
        System.out.println(answer);
    }
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/89cea7e2aecf443206fd39c191d9a6833744022a

백준_1300, K번째 수 · Heron-Woong/CodingTest_Practice@89cea7e