이진탐색 문제는 문제의 규칙을 이해하고 어떻게 적용할 수 있는지를 찾는 것이 중요하다고 느꼈다.
===========================================
문제
세준이는 크기가 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*N 배열을 만들었을 때 [1,1],[2,2], ... , [N,N] 칸에 있는 숫자인 줄 알았다.
필요한 칸의 노드가 몇 번째 대각선 사이에 있고 두 대각선을 찾았을 때 그 사이에 필요한 칸의 노드가 몇번째로 존재하는지 검사하면 값을 찾을 수 있으리라 생각했다.
대각선에 들어갈 수 있는 공식은 구하였으나 문제는
4와 9 사이에는 4 4 6 6 5 5 8 8 가 있는데 문제에서는 정렬을 한다고 했으니 4 4 5 5 6 6 8 8이 되어서 이 방법으로는 정렬된 값만을 탐색할 수 있는 이진탐색을 적용할 수 없었다.
몇 시간 고민했으나 풀이가 떠오르지 않아 솔루션을 보았다.
예시 그림
ex) K = 22일 때 arr[K] = 16
핵심 1-1. K번째 수(arr[k])는 K보다 무조건 작다.
핵심 1-2. K는 K번째 수보다 무조건 크다.
핵심 2. K아래에는 K보다 작은 수가 K-1개만큼 존재한다.
K보다 작은 수를 구하는 방법은 배열의 행 첫번째 자리로 K를 나눈 뒤 모두 합하는 것이다.
K = 22일 때 1행: 5, 2행: 5, 3행: 5, 4행: 5, 5행: 4 로 총 24개가 나온다.
K 아래에는 21개밖에 나올 수 없기 때문에 값을 낮춰서 다시 계산한다.
여기서 이진탐색의 개념을 적용할 수 있다.
left = 1, right = K = 22(핵심 1-2를 고려했을 때)로 이진탐색을 시작한다.
첫 mid값은 11이고 배열에서 11보다 작은 수는 17개이므로 21개가 안되기 때문에 left = mid+1로 변경한다.
left = 12, right = 22, mid = 17
17보다 작은 수는 22개이므로 21개보다 크기 때문에 right = mid-1로 해준다.
이것을 반복해서 left가 right보다 클 때까지 반복해주면 된다.
mid가 해당 값과 일치해도 끝까지 수행해주어야 하는 게, 이 배열은 대각선을 기준으로 대칭이므로 같은 숫자가 2개 이상 나오는 경우가 존재한다. 같은 수 끼리는 같은 값이 나오기 때문에 마지막까지 left, right를 좁히며 K번째 수를 구하면 된다.
자바 코드 clickimport java.util.Scanner;
public class BOJ_1300_G2_K번째수 {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = s.nextInt();
long K = s.nextInt();
long left = 1;
long right = K;
long ans = 0;
while (true) {
if (left > right)
break;
long mid = (left + right) / 2;
long cnt = 0;
for (int i = 1; i <= N; i++) {
cnt += Math.min(mid / i, N);
}
if (cnt >= K) {
ans = mid;
right = mid - 1;
} else if (cnt < K) {
left = mid + 1;
}
}
System.out.println(ans);
}
}
