알고리즘 챌린지 4일차

문제

문제: 백준 알고리즘 1300번 K번째 수

풀이

• 시작 인덱스를 1, 마지막 인덱스를 K로 대입해준다.
• 이진 탐색을 수행하면서 중앙값보다 작거나 같은 값이 몇 개인지 카운트한다.
• 카운트한 값이 K보다 작으면 시작인덱스를 중앙값+1로 바꾼다.
• 카운트한 값이 K보다 답에 중앙값을 넣고 마지막 인덱스를 중앙값-1로 바꾼다.
• 시작인덱스가 마지막인덱스보다 커지면 탐색을 종료하고 답을 출력한다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan =new Scanner(System.in);
        int N=scan.nextInt();
        int K=scan.nextInt();
        long start=1,end=K;
        int count=0;
        long answer=0;
        
        while(start<=end){
            long mid=(start+end)/2;
            count=0;
            for(int i=1;i<=N;i++){
                count+=Math.min(mid/i,N);
            }
            if(count<K){
                start=mid+1;
            }else{
                answer=mid;
                end=mid-1;
            }
        }
        System.out.print(answer);

    }
}

정리

작은 수의 개수가 k-1인 중앙값을 찾는 것이 이 문제의 포인트이다. 정렬되어 있고 탐색이니 이진 탐색을 이용한다. 하지만 이진 탐색을 사용한다는 것을 알아도 쉽지않았다. 이진 탐색 유형의 알고리즘 문제를 많이 풀어보자!