[백준/JAVA] 1300번: K번째 수

🔺 문제

1300번: K번째 수

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());
 
        long start = 1;
        long end = k;
        long answer = 0;
 
        // 이진 탐색
        while(start <= end) {
            long mid = (start + end) / 2;
            long cnt = 0;    // k보다 작은 수
 
            for(int i = 1 ; i <= N ;  i++) {
                cnt += Math.min(mid / i, N);    // 작은 수 카운트
            }
 
            if(cnt < k) {
                start = mid + 1;
            }
            else {
                answer = mid;   // 현재 단계 중앙값을 정답 변수에 저장
                end = mid - 1;
            }
        }
 
        System.out.println(answer);
    }
}

 

✅ 해결 아이디어
✔ 이진 탐색 !
- 중앙값보다 작은 수의 개수를 세면서 이진 탐색으로 정답 구하기.
(= 정답 : 작은 수의 개수가 k-1개인 중앙값)
- B[k] = x의 의미는 x보다 작같은 원소 개수가 최소 k개라는 의미

 

💥 유의사항

⇨ 이분 탐색, 무엇을 범위로 잡을지 (start와 end 범위)

⇨ 무엇을 기준으로 나눌지

 

 

---

🔺 다른 풀이들

[백준] 1300번 : K번째 수 - JAVA [자바]

최고의 설명.. 최고의 풀이....👍👍👍👍👍

---

💬 느낀 점

실제로 배열을 생성하지 않고, 저렇게 인덱스랑 값만 쏙 빼와서 사용하는 게 넘 신기하다.....

그리고 생각보다 코드도 간단해서 놀람,,,,,

물론 저걸 작성하기 위해 아이디어를 생각하기까지 오래 걸리지만,,,,ㅠ

 

 

1회독	2회독	3회독	4회독	5회독
V	6/18