BOJ_1300 : K번째 수

👉 문제링크

1300번: K번째 수

---

---

🔸 문제 분석 🔸

• N x N 인 배열 A가 있고, A[i][j] = ixj 이다.
• 일차원 배열 B에 A를 넣고 오름차순 정렬했을 때, B[k]를 구한다.
• 배열 인덱스는 1부터 시작한다.

🔸 문제 풀이 🔸

• 배열 A의 원소들 중 중앙값 보다 작은 수들의 개수를 세며 이진 탐색을 통해 풀이한다.
  • 중앙값 보다 작은 수들이 K보다 작다면, 시작 인덱스를 중앙값 +1 로 변경한다.
  • 중앙값보다 작은 수들이 K이상이라면, 마지막 인덱스를 중앙값 -1 로 변경한다.
  • 시작 인덱스와 마지막 인덱스가 교차되었을때, 시작 인덱스가 탐색 결과이다.

🔸 코드 🔸

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());

        int start = 1;
        int end = K;

        while (start <= end) {
            int mid = (start + end) / 2;
            int cnt = 0;
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(N, mid / i);
            }
            if (cnt < K) start = mid + 1;
            else end = mid - 1;
        }

        bw.write(Integer.toString(start));
        bw.flush();
    }
}

🔸 코드 해석 🔸

• 이진 탐색으로 중앙값보다 작은 원소의 수를 세며 계산한다.
  • 중앙값을 배열 A의 행 인덱스로 나눈 몫은, 해당 행에서 중앙값보다 작거나 같은 원소의 수이다.
    (단, N보다 크다면 N이 중앙값보다 작은 원소 수가 된다.)
  • 중앙값보다 작은 원소의 수가 K보다 작다면, K번째 수는 더 큰쪽에 존재한다.
    • 중앙값보다 큰 쪽을 탐색하기 위해 start를 mid+1로 늘리고 탐색한다.
  • 중앙값보다 작은 원소 수가 K 이하라면, K번째 수는 같거나 더 작은 쪽에 존재한다.
    • 중앙값보다 작은 쪽을 탐색하기 위해 end를 mid - 1로 줄이고 탐색한다.
  • start와 end가 교차되었을 때, start가 탐색 결과이다.

---

🔸 end 🔸

• 이 문제는 이진 탐색이라는 것을 파악하는 것 부터가 어려운 문제라고 한다.
  • 교재를 통해 풀이 방법을 먼저 살펴보고 풀이를 해보아서 바로 맞았지만, 혼자 풀었으면 절대 못풀었을 것 같다.
  • 이런 매개 변수 탐색 방식은 정말 기발한 풀이가 많은 것 같고, 아직 한참 연습해야 할 것 같다.