[Java] [백준 1300][이분 탐색, Parametric Search] 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]를 출력한다.

---

BOJ 1300: K번째 수

🌈 풀이 후기

• 처음에 단순하게 배열에 넣어서 검사하려다가 범위가 너무 커서 메모리 오류가 났습니다. 범위를 잘 파악하고 문제를 시작해야 시간낭비를 줄일 수 있을것 같습니다.
• 곰곰히 생각해보니 이전에 풀다가 실패했던 유형과 비슷했습니다. (백준 1477 휴게소 세우기) 당시 이분 탐색을 응용해서 푸는 문제였는데 이해가 잘 안가서 잠시 미뤘던 문제였습니다. 아직까지 이분 탐색 문제에 자신이 좀 없어서 이번 기회에 차근차근 공부했습니다. 아직 완벽하게 이해하지는 못했지만 백준 문제집을 따로 만들어 놨습니다. 천천히 풀어볼 생각입니다.!!
  
  
• 이 문제는 Parametric Search 라고 불리는 문제입니다. 최적화 문제를 결정 문제로 바꿔서 풀어야 하는데 1~10까지 있을때 5가 조건을 충족하지 않으면 1~5번 모두 조건을 충족하지 않기에 5~10번을 다시 검사하면 되는 방식입니다. 관련 개념은 밑에 블로그에 잘 정리되어 있으니 한번 읽어보세요!!

파라매트릭 서치(Parametric Search)

👩‍🏫 문제 풀이

알고리즘 - Parametric Search ( 이분탐색 유사)

1. K번째 수를 찾기 위해서 1과 K를 left, right로 잡고 이분 탐색을 한다.

2. mid값을 기준으로 NN 에서 ij가 mid보다 작은 값들의 수를 체크한다.

3-1. 만약 mid보다 작거나 같은 수의 개수의 합이 K보다 작다면 1~mid 사이의 값들은 조건에 충족되지 않기에 mid+1부터 다시 검사한다.

3-2. 만약 mid보다 작거나 같은 수의 개수의 합이 K보다 같거나 크다면 K번째 수의 조건을 충족한다. 하지만 이 mid값이 최소값인지는 알 수 없기에 left부터 mid-1 까지 다시 검사한다.

4. 만약에 left가 right보다 크다면 더이상 검사가 불가능하니 left를 return한다. (left를 return은 그 조건을 충족하는 것중에서 가장 작은 값이기 때문이다. left를 return하지 않고 K번째 수의 조건 충족하는 Mid값을 따로 저장한 뒤에 그 값을 return 해줘도 된다.)

 

*  이때 mid보다 작거나 같은 수의 개수의 합을 구하는 것이 중요한데 특정한 규칙을 따른다.

 

ex) N 이 3, K가 7인 경우

 

1 2 3 → 1의 배수(i==1)

2 4 6 → 2의 배수 (i==2)

3 6 9 → 3의 배수 (i==3)

 

N이 3이고 K가 7이기에 현재 mid는 5 .

 

mid가 5이기에 5보다 작은 수들은 각 행별로 3개(1,2,3), 2개(2,4) ,1개(3) 이다. 총 6개 이다.

 

이 수들을 파악하는 규칙은 각 행들은 각 행들의 배수가 연속적으로 있다.

 

1행은 1의 배수들, 2행은 2의 배수들, 3행은 3의 배수들이다.

 

따라서 한 행에서 최대 N이며 mid / i (현재 행) 이다.

 

i==1 ⇒ Math.min(N , mid/i) ⇒ 3

i==2 ⇒ Math.min(N , mid/i) ⇒ 2

i==3 ⇒ Math.min(N , mid/i) ⇒ 1

package com.Boj.seoul8.week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

// 이분 탐색 
// Parametric Search => N*N 에서 x 이하의 수가 K개 이상이다. 
// O(logN)
public class BOJ_G3_1300_K번째수 {
	static int N, K;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		K = Integer.parseInt(br.readLine());

		System.out.println(binarySearch(1, K));

	}

	private static int binarySearch(int left, int right) {

		if (left > right)
			return left;

		int mid = (left + right) / 2;
		int cnt = 0;

		// 각 행별로 mid보다 작은수의 개수를 더해준다.
		for (int i = 1; i <= N; i++) {
			cnt += N > mid / i ? mid / i : N; // == Math.min(mid/i ,N)
		}
		// mid보다 작거나 같은 수의 합이 K보다 작다는 것은 mid 이하는 탐색할 필요가 없다는 것이다.
		// 같으면 K번째 수가 될 수는 있지만 최소값인지는 알 수 없다.
		if (cnt < K) {
			return binarySearch(mid + 1, right);
		} else {
			// K보다 커서 가능한 경우들. 최소값인지 모르기에 범위를 좁혀나간다.

			return binarySearch(left, mid - 1);
		}
	}

}