031 : 배열에서 K번째 수 찾기

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        // Preprocessing
        long start = 1, end = K;
        long ans = 0;

        // Operating session : Binary Search
        while (start <= end) {
            long middle = (start + end) / 2;
            long cnt = 0;
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(middle/i, N);
            }

            if (cnt < K) {
                start = middle + 1;
            } else {
                ans = middle;
                end = middle - 1;
            }
        }
        // Output Supply Cable
        System.out.println(ans);
    }
}

 

 

Briefing
문제	단 하나의 맥락	입출력과 되어야 하는 것(현실에서 구현부)
- 크기가 N x N인 배열 - 들어있는 수는 A[i][j] = i x j - 이 수를 1차원 배열 B에 넣으면 B의 크기는 N x N이 된다 - B를 오름차순 정렬하였을 때, B[k]를 구하라	value가 중복되어 있어서 오름차순 정렬이 어렵다 B[k]는 k보다 작은 수(v)들이 k-1개(i의 갯수)이므로 공간을 1~K로 시작하는 binary search 사용	I // 배열의 크기 N k O // B[k]

 

흐름
입력 파이프라인	전처리 및 maneuvering	출력 파이프라인

 

(모듈과 사고 경향)

- 작은 수의 개수가 k-1 개인 중앙값을 찾는 방식으로 k를 찾기

- 2차원 배열에서의 k번째 수는 k를 넘지 않음, 2차원 배열의 1~k번째 안에 정답이 있음

- 중앙값보다 작거나 같은 수의 갯수는(cnt) 중앙값을 N으로 나눈 값, 단 나눈 값이 N보다 크면 N으로 정함

 

// Preprocessing
long start = 1, end = K;
long ans = 0;

- start와 end는 BInary Search가 진행되는 공간을 만드는 양 끝점

- ans는 출력 케이블을 연결하는 joint

// Operating Session : Binary Search
while (start <= end) { // 항상 공간 먼저
    // 시행부
    long middle = (start + end) / 2; // 전체 위상을 가져가는 변수정의
    long cnt = 0; // plating (한 곳으로 수렴하는)
    
    for (int i = 1; i <= N; i++) { // i가 0사용 불가하므로, 1부터 N까지
        cnt += Math.min(middle/i, N); // 예외 처리
    }
    // 조건, 판단부
    if (cnt < K) {
        start = middle + 1;
    } else { 
        ans = middle;
        end = middle - 1;
    }
}

- start와 end가 공간이었다면, 

- cnt와 K는 기준과 비교점(DFS의 boolean visited처럼)

 

(주의 / 실수 / 헷갈림 / 절차적 부분 / 의문)