[PS] 백준1300 : K번째 수(Java)

문제

https://www.acmicpc.net/problem/1300

1300번: K번째 수

---

풀이

파라메트릭 서치를 활용한 풀이

그리디한 접근법

A[i][j]값을 1차원 배열에 기록 후 오름차순 정렬을 통해 원하는 값 B[K]를 구하는 방식

해당 방식으로 풀이하게 될 경우 N^2만큼의 메모리가 필요할 뿐더러 시간 또한 O(N^2)만큼 걸리기 때문에 AC를 받을 수 없음

 

---

LowerBound 접근

위의 방식에서 이분탐색을 추가해서 탐색 시간을 줄여야하는데 어떤식으로 이분탐색을 활용할지 잘 떠오르지 않아 상당히 고생함..

해당 문제를 이분탐색으로 접근하기 위해서는 우선 몇가지의 이해가 필요함

1. 입력에서 주어지는 K는 1차원 배열 B에서 K와 같거나 보다 작은 원소의 개수를 뜻함.
2. 임의의 값 x보다 작거나 같은 원소의 개수를 구하기 위해서는 각 행의 번호를 i라고 두면 x/i는 i행에서의 x보다 작은 값의 개수가 나옴.

즉, 전체 배열 N*N에서 x보다 작거나 같은 원소의 개수를 구하는 코드를 보면 아래와 같음.

for(int i=1; i<=N; i++) {       //mid값보다 작은 원소의 개수를 구하는 과정
	cnt += Math.min(mid/i,N);       //각 행에서 mid보다 작은 원소의 개수는 최대 N개를 넘어가지 않기 때문에 추가적인 비교 필요.
}

 

간단하게 우리가 구하고자 하는 B[K]의 값을 x라고 두면, x를 구하기 위해 이분탐색으로 위 1번의 내용을 비교하여 구하면 됨.

 

매 탐색마다 임의의 값 mid보다 작거나 같은 원소의 개수를 구한 후 아래의 비교를 진행

1. K ≤ cnt : 임의의 값 mid는 K보다는 큰 값이라는 것을 의미
2. K > cnt : 임의의 값 mid는 K보다 작은 값이라는 것을 의미

이분탐색으로 구해진 값은 작거나 같은 원소의 개수가 8과 같거나 큰 값이 처음으로 나오는 위치인 걸 알 수 있음. (아래 그림에서는 4가 구해짐)

 

해당 이분탐색을 진행할 때 Lower-Bound로 구해야 함.

Upper-Bound로 진행하게 될 경우

위와 같은 N = 4인 B 배열에서 B[8]을 구하고자 할 때 임의의 값이 5가 될 경우 5보다 작거나 같은 원소의 개수는 8로 K와 같은 값이 되므로 x는 6이 되기 때문에 정해를 구할 수 없게 됨.

 

즉, Lower-Bound로 진행하는 이유는 임의의 값 mid가 갖는 작거나 같은 원소의 개수가 찾고자 하는 값K(8)와 같거나 큰 값이 처음 나오는 위치를 구해야 하기 때문임.

 

---

소스코드

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

//BOJ_1300 K번째 큰 수
public class Main {
    static int N, K;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); //수열의 크기
        K = Integer.parseInt(br.readLine()); //구하고자 하는 원소 위치

        System.out.println(BinarySearch(K));

    }

    /*
    * K값은 즉 구하고자 하는 값 x보다 작은 원소의 개수를 뜻함
    * 이분탐색을 통해 K보다 같거나 큰값이 처음 나오는 위치를 구하면 됨.
    * 비교하는 값은 cnt로 임의의 값 mid보다 작은 원소의 개수를 구한 후 비교 진행
    */
    private static int BinarySearch(int key) {
        int low = 1;
        int high = key;

        /* LowerBound */
        while(low < high) {
            final int mid = (low+high) / 2;

            long cnt = 0;

            for(int i=1; i<=N; i++) {       //mid값보다 작은 원소의 개수를 구하는 과정
                cnt += Math.min(mid/i,N);       //각 행에서 mid보다 작은 원소의 개수는 최대 N개를 넘어가지 않기 때문에 비교
            }

            if(cnt >= key) {        //key값보다 작은 원소가 더 많을 경우 범위를 줄여서 탐색
                high = mid;
            }
            else {                  //key값보다 작은 원소가 적다면 범위를 올려서 탐색
                low = mid + 1;
            }

        }
        return low;
    }
}

 

---

정리

이번 문제를 풀기 위해서 이해를 하고 있어야 하는 내용들이 좀 있다는 걸 알 수 있음.

 

문제를 풀 때 주어지는 조건들로 하여금 어떤 추가적인 내용을 알 수 있는지 탐색을 먼저 해보는 경우도 있어야 한다는 걸 알 수 있었음.

위 문제를 예로들면 배열의 인덱스는 해당 값 x가 가지는 작거나 같은 원소의 개수를 나타낸다는 것.

 

또한 LowerBound와 UpperBound의 차이점을 좀 더 명확히 이해하기 위해 추가적인 정리가 필요한 것을 느꼈음…. 추후에 비교 포스팅을 해야할 것 같음..

 

---

Reference

LowerBound vs UpperBound

https://jackpot53.tistory.com/33

이진탐색-상/하한선((lower bound,upper bound)