[이분탐색] - gpt 문제 1

 

1. K번째 수 찾기

 

 

gpt가 알려준 코드

 

left = 1

right = N*N 으로 해서

이분탐색

public class KthSmallest {
    
    // x 이하의 수가 배열에서 몇 개인지 세는 함수
    public static int countLessEqual(int N, int x) {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            count += Math.min(x / i, N);  // x 이하의 수는 i행에서 x//i개까지 존재
        }
        return count;
    }

    // K번째 작은 수를 찾는 함수
    public static int findKthSmallest(int N, int K) {
        int low = 1, high = N * N;
        
        while (low < high) {
            int mid = (low + high) / 2;
            
            // mid 이하의 수가 K개보다 적으면 low를 증가시킴
            if (countLessEqual(N, mid) < K) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        
        return low;  // low가 K번째 작은 수
    }

    public static void main(String[] args) {
        // 예시 1
        int N = 3;
        int K = 5;
        System.out.println(findKthSmallest(N, K));  // 출력: 3

        // 예시 2
        N = 4;
        K = 7;
        System.out.println(findKthSmallest(N, K));  // 출력: 6
    }
}

 

 

이 중에서 아래 메서드에 대해 설명하자면

public class KthSmallest {
    
    // x 이하의 수가 배열에서 몇 개인지 세는 함수
    public static int countLessEqual(int N, int x) {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            count += Math.min(x / i, N);  // x 이하의 수는 i행에서 x//i개까지 존재
        }
        return count;
    }