[백준 1300] K번째 수 (JAVA)

백준 1300번 문제  - K번째 수 

1300번: K번째 수

---

문제 분석

 

• N*N 배열을 1차원 배열로 정렬해서, k번째 수를 출력해라

---

 

해결 키 포인트

 

• 이진탐색으로 해결한다는 마인드를 가져야 함 (본인도 이를 못해서 힌트를 찾음)
  • NxN배열에서 k보다 큰 수를 배열을 만들어서 정렬한 뒤 찾으려면 메모리 초과로 불가능
• n보다 큰 값은 i번째의 행의 i / n 개의 수가 존재한다.
  • 3X3배열에서  4보다 큰 값

1번째 행	4 / 1	3
2번째 행	4 / 2	2
3번째 행	4 / 3	1

• 이렇게 각 행의 개수를 합하면 총 배열의 개수를 알 수 있다. 그 개수가 동일할 때, start값을 출력하면 해당 값이 배열의 k번째 값이다.

---

이진 탐색

 

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙 값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

알고리즘

 

1. 현재 데이터셋의 중앙값을 선택
2. 중앙값 > 타깃 데이터 일 때 : 중앙 값 기준으로 왼쪽 데이터 셋 선택
   중앙값 < 타깃 데이터 일 때 : 중앙 값 기준으로 오른쪽 데이터 셋 선택
3. 과정 1~2를 반복하다, 중앙값 == 타깃 데이터 일 때 : 탐색 종료

Do It! 알고리즘 코딩 테스트

 

---

코드

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // k 입력
        int k = Integer.parseInt(br.readLine());

        // 이진 탐색 변수
        int start = 1;
        int end = k;

        // k값보다 큰 값은 i번째 행의 k/i개의 수가 존재한다는 개념이 중요
        // 최소 값이 최대 값보다 커질 때까지
        while(start <= end) {
            // 중앙 점
            int mid = (start + end) /2;

            // 현재 중앙 점
            int count = 0;
            for(int i=1;i<=N;i++){
                // mid/i랑 N중에 작은 값으로 count 증가
                count += Math.min(mid/i, N);
            }
            // count가 k보다 클경우 end 축소
            if(count >= k)
                end = mid-1;
            // count가 k보다 작을경우 end 확대
            else
                start = mid+1;
        }

        System.out.println(start);
    }
}