[백준_1300번] K번째 수

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은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, N2)보다 작거나 같은 자연수이다.

 

[코드]

import java.util.*;

public class BaekJoon_1300 {
	public static int n,k;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		k=sc.nextInt();
		
		/*
		 * 배열의 인덱스가 1부터 시작하기 떄문에 start는 최솟값 1로 초기화 한다.
		 * k번째에 해당하는 수는 k를 초과하지 않기 때문에 end 값을 k로 초기화 한다. 
		 * 그 이유는 두 개씩 중복되는 수가 존재하기 때문이다.   
		 */
		long start=1;
		long end=k;
		long result=0;
		
		// 이분탐색
		while(start<=end) {
			long mid=(start+end)/2;
			long count=0;
			
			/*
			 * Math.min(mid/i, n)에서 mid/i는 각 행에서 mid보다 작은 숫자의 개수를 의미한다.
			 * 이때 만약 n=4, mid=7이라고 가정하면 1행에서는 7/1=7의 결과가 나오는데
			 * 각 행에 있는 숫자의 개수는 최대 n개이기 떄문에 mid/i or n 중 작은 숫자를 누적해나가면서
			 * mid보다 작은 숫자의 개수를 새나간다.
			 */
			for(int i=1;i<=n;i++)
				count+=Math.min(mid/i, n);
			
			/*
			 * mid보다 작은 숫자의 개수가 k보다 작다면 mid는 k번째 수가 될 수 없기 때문에
			 * 좀 더 큰 숫자를 탐색하기 위해 범위를 크게 한다.
			 * 
			 * mid보다 작은 숫자의 개수가 k보다 크다면 mid는 k번째 수에 포함된다.
			 * 따라서 mid를 result에 저장하고 범위를 좁혀 재탐색한다.
			 */
			if(k>count)
				start=mid+1;
			else {
				result=mid;
				end=mid-1;
			}	
		}
		System.out.println(result);
	}
}

 

[알고리즘]

 이분탐색을 위한 start 값은 최솟 값이 되는 1로 초기화, end 값은 최댓 값이 되는 k로 초기화 한다. k 번째 값은 중복되서 나타나는 값들로 인해 k를 넘을 수 없기 때문이다. 이렇게 이분탐색을 진행하면서 mid 값을 계산하고, 1행 부터 n번째 행 까지 각 행에서 mid값과 같거나 작은 수들을 count 한다. 이때 count는 count+=Math.min(mid/i, n)로 구할 수 있다.

 

예를 들어 n=4, k=7인 경우 count 값을 구해보자. 우선 nXn 행렬을 채워보면 아래와 같다.

i/j	1열	2열	3열	4열
1행	1	2	3	4
2행	2	4	6	8
3행	3	6	9	12
4행	4	8	12	16

 

mid 값이 6이라면 count(6보다 작은 숫자의 개수)는

i=1 -> 1, 2, 3, 4 (6/1 = 6, 해당 값은 n의 개수를 넘었기 때문에 최대 개수인 n을 count에 누적) 

i=2 -> 2, 4, 6 (6/2 = 3, n보다 작기 때문에 해당 값을 count에 누적)

i=3 -> 3, 6 (6/3 = 2, n보다 작기 때문에 해당 값을 count에 누적)

i=4 -> 4 (6/4 = 1, n보다 작기 때문에 해당 값을 count에 누적)

4 + 3 + 2 + 1 = 10이다. 즉, 6은 최대 10번째에 해당한다는 말이다.

 

이렇게 구한 count의 값이 구하고자 하는 k번째 보다 큰 경우는 mid가 k번째 수에 포함되기 때문에 결과 값을 저장하고, 숫자를 낮춰서 재탐색한다. 반면에 count가 k번째 보다 작은 경우는 mid가 k번째 수에 포함되지 않기 때문에 개수를 늘리고자 숫자를 높여 재탐색 한다.

 

[고찰] 

 해당 문제를 풀기 위해 스스로 다양한 방법들을 고민해 보았지만 쉽게 떠오르지 않아 다른 사람들의 풀이법을 참고하였다. 처음에는 count 값을 구하는 방식이 이해가 가지 않았지만 표를 그려보며 직접 count 값을 구해보니 이해가 되었다. 여러번의 복습이 필요한 문제같다.