[BAEKJOON] 1300 K번째 수

문제 요약

• 알고리즘 분류: 이분탐색
• 난이도: Gold2
• 문제내용:
  • 크기 N×N 배열이고 시작 인덱스는 0이 아니고 1부터 시작한다.
  • 배열 A[i][j]의 값은  i × j이다. 
  • 2차원 배열 A를 일차원 배열 B로 만들어서 오름차순으로 정렬하면 배열 B에서 K번째 인덱스 값을 구해라

• 사이트: https://www.acmicpc.net/problem/1300

1300번: K번째 수

문제풀이

 이번 문제는 간단해 보일거 같은데.. 배열 A에서 완전탐색으로 값을 넣고 B로 일렬로 만들어서 정렬한다음 K번째 인덱스 위치 값 반환 이런식으로 풀면 N의 크기가 10만이고 시간복잡도는 O(N ^ 2)이므로 시간 초과가 날것이다. 저 문제를 풀라면 O(logN)시간안에 풀어야 통과가 된다. 그래서 이번 문제의 핵심 알고리즘 O(logN)으로 풀수 있는 이분 탐색이다. 이분탐색의 자세한 설명은 아래 사이트에서 확인 하면된다.

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89 

이진 탐색 - 나무위키

문제 접근 방법

왼쪽은 A 오른쪽은 B

 예제를 위 표로 표현 한것이다. 왼쪽은 A 배열이라고 하고 오른쪽은 A배열을 일차원으로 변경후 오름차순으로 정렬한 B배열이라고 보면 오른쪽의 표를 보면 인덱스의 위치 와 값을 비교해보면 인덱스 위치 <= 값 이라고 볼 수가 있다. 그렇다고 인덱스 위치 <= 값 이 내용만으로도 이분탐색 하기는 힘들다. 그래서 그 다음으로 봐야 할것은 값의 순위를 봐야 한다.

• 1 보다 이하인 수: 1개
• 2 이하인 수 : 3개
• 3 이하인 수 : 5개
• 4 이하인 수 : 6개
• 5 이하인 수 : 6개
• 6 이하인 수 : 8개
• 7 이하인 수:  8개
• 8 이하인 수:  8개
• 9 이하인 수: 10개

예제에서 찾고 싶은 인덱스는 7이다. 하지만 A 배열에서 7라는 수는 없다. 그래서 위에 7이하인 개수가 8개이고 같은 8개중 가장 낮은 숫자가 6이다.  그래서 결론은 동일한 개수 중 가장 낮은 수는 A 배열에 존재 한다는 것을 알수 있다. 그 이유는 개수가 변화되는 시점이고 변화가 될려고 하면 배열안에 값은 무조건 있어야 된다는 것이다. 그래도 이해가 안되면 N과 K를 다른 수를 예시로 해서 A4용지에 문제 접근 방법 처럼하면 알 수 가 있다. 이 내용을 이해가 되면 다음에는 개수를 구하는 방법을 알면 된다.

 일 단 A 배열은 1 ~ N 까지의 구구단이라고 생각하면되고 중간 값을 value라고 하면 각 행마다 현재 값보다 낮은 개수(value/ 행 번호 = j의 위치 반환)를 더하면된다. 하지만 각 행의 최대 개수는 N이라서 (value/ 행 번호 > N)크면 범위가 넘어가서 넘어간 경우에는 N이라고 하면된다. 그래서 결론으로는 min(value / 행 번호, N)이런 식으로 된다. 그 다음에는 K의 수가 중간값의 개수보다 낮은면 start 값을 m + 1로 하고 크거나 같으면 end 값을 m - 1로 범위를 줄이면서 탐색 하면된다.

정리

1. start는 1(인덱스 1부터 시작해서 1로 세팅함) end는 N * N으로 설정한다.
2. 중간값이하의 개수를 구한다.
3. 중간값이하의 개수보다 작으면 start값은 m - 1, 중간값보다 크거나 같은면  m + 1로 값을 설정 한다.
4. 값의 범위가 1로 될때  start값을 출력하면된다.

Code

Python

N = int(input())
K = int(input())

start = 0
end = N * N
while start <= end:
    mid = (start + end) //2
    count = 0
    for i in range(1, N + 1):
        count += min(mid // i, N)
    if count >= K :
        end = mid - 1
    else:
        start = mid + 1

print(start)

Java

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long N = Long.parseLong(br.readLine());
		long K = Long.parseLong(br.readLine());
		
		long start = 1;
		long end = N * N;
		long mid, count, i;
		while(start <= end) {
			mid = (start + end) / 2;
			count = 0;
			for(i = 1; i <= N; i++) {
				count += Math.min(mid / i, N);
			}
			
			if(count >= K) {
				end = mid -1;
			}else {
				start = mid + 1;
			}
		}
		System.out.println(start);
	}
		
}