BOJ_12991_홍준이의 행렬 (Java)

[Gold I] 홍준이의 행렬 - 12991

문제 링크

성능 요약

메모리: 31356 KB, 시간: 552 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2025년 2월 20일 16:26:32

문제 설명

홍준이에게는 길이가 N인 수열 2개 A와 B가 있습니다. 이때 N² 크기의 행렬을 만드는데, 행렬의 i행 j열의 원소는 수열 A의 i번째 원소와 수열 B의 j번째 원소의 곱으로 정의합니다. 홍준이는 이 원소들을 모두 정렬하였습니다.

홍준이는 정렬된 결과에서 K번째(1번부터 계산)에 위치하는 값이 궁금해졌습니다. 하지만 계산이 느린 홍준이는 정렬하는데 너무 시간이 오래 걸리기 때문에 여러분에게 도움을 요청하였습니다. 홍준이를 도와 K번째 원소의 값을 구하는 프로그램을 작성하세요.

입력

첫째 줄에 N과 K가 주어집니다. (1 ≤ N ≤ 30000, 1 ≤ K ≤ N²)

둘째 줄에 수열 A의 원소를 나타내는 N개의 정수가 공백을 사이에 두고 주어집니다.

셋째 줄에 수열 B의 원소를 나타내는 N개의 정수가 공백을 사이에 두고 주어집니다.

각 수열의 원소들은 1 이상 10억 이하의 자연수입니다.

출력

N² 크기의 행렬에서 K번째로 작은 수의 값을 출력합니다.

문제 풀이

이분탐색을 2번 활용해주었다.

코드

package BOJ_12991_홍준이의행렬;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, K;
    static long res;
    static long[] A, B;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_12991_홍준이의행렬/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        A = new long[N];
        B = new long[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(A);
        Arrays.sort(B);

        long left, right;
        left = A[0] * B[0];
        right = A[N - 1] * B[N - 1];

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (count(mid)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        System.out.println(res);
        bw.flush();
        bw.close();
        br.close();
    }

    private boolean count(long target) {
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            int tmp = 0;
            int left = 0, right = N - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (A[i] * B[mid] <= target) {
                    tmp = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            cnt += tmp;
        }
        return cnt >= K;
    }
}