[코딩테스트] 백준 1300 자바

백준 1300

백준 1300 문제

해당 문제는 이진 탐색으로 중앙값보다 작은 수의 개수를 세면서 범위를 절반씩 줄이는 방법으로 B[k]값을 구하면 된다.

다시 말하면 작은 수의 개수가 k - 1개인 중앙값이 정답이다.

작은 수의 개수를 세는 아이디어가 이 문제를 푸는 열쇠이다.

import java.util.Scanner;

public class Boj1300 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 배열의 크기
        int k = sc.nextInt(); // 구하고자 하는 index
        long start = 1; // 시작 인덱스
        long end = k; // 종료 인덱스
        long answer = 0; // 정답

        // 이진 탐색 수행
        while (start <= end) { // 시작 인덱스가 종료 인덱스보다 작거나 같으면 반복
            long mid = (start + end) / 2; // 중간 인덱스
            long count = 0; // 중앙값보다 작은 수

            // 중앙값보다 작은 수는 몇개인지 계산
            for (int i = 1; i <= n; i++) { // n의 개수만큼 반복
                count += Math.min(mid / i, n); // count에 중앙 인덱스를 i로 나눈 값과 n중 작은 값을 더함, 작은 수를 카운트하는 핵심 로직
            }

            if (count < k) { // 현재 중앙값보다 작은 수의 개수가 k보다 작으면
                start = mid + 1; // 시작 인덱스를 중간 인덱스 + 1로 변경
            } else { // 현재 중앙값보다 작은 수의 개수가 k보다 크거나 같으면
                answer = mid; // 정답 변수에 현재 단계의 중앙값을 저장
                end = mid - 1; // 종료 인덱스를 중간 인덱스 - 1로 변경
            }
        }

        System.out.println(answer); // 정답 출력
    }
}

문제 풀이

1. 배열의 크기를 n에 저장한다.
2. 구하고자 하는 인덱스를 k에 저장한다.
3. 시작 인덱스 start를 1로 저장한다.
4. 종료 인덱스 end를 k로 저장한다.
5. 정답 answer를 0으로 저장한다.
6. 시작 인덱스가 종료 인덱스보다 작거나 같으면 반복하며 이진 탐색을 수행한다.
7. start와 end의 중간 인덱스를 mid에 저장한다.
8. mid보다 작은 수를 저장하는 count를 0으로 저장한다.
9. n의 개수만큼 반복하며 중앙값보다 작은 수는 몇개인지 계산한다.
10. count에 중간 인덱스를 i로 나눈 값과 n중에서 작은 값을 더한다. (이는 작은 수를 카운트하는 핵심 로직인다.)
11. count가 k보다 작으면 start를 mid + 1로 변경한다.
12. count가 k보다 크거나 같으면 answer에 현재 mid값을 저장하고, end를 mid - 1로 변경한다.
13. 이진 탐색이 종료되면, answer를 출력한다.