[Java]자바로 이진탐색 연습2 -올바르게 사고하기-

1. 문제

 

n개의 점과 m개의 선분이 주어질 때, 각 선분 위에 몇개의 점이 있는지 구하는 프로그램을 작성해보세요.

 

첫 번째 줄에 n과 m이 공백을 두고 주어집니다.

두 번째 줄에는 점의 좌표가 공백을 사이에 두고 주어집니다.

세 번째 줄부터 m개의 줄에 걸쳐 선분의 시작점과 끝점이 공백을 두고 한 줄에 하나씩 주어집니다.

• 1 ≤ n, m ≤ 100,000
• 1 ≤ 주어지는 수 ≤ 1,000,000,000

 

3 4
10 30 50
1 5
5 21
22 59
210 293

 

 

2. 풀이

 

아무 생각없이 사고 한다면...

 

선분의 시작점 끝점 예를 들어 1 5를 기준으로, 여기에 점의 좌표 10,30,50이 들어있는지 검사해보는 식으로

 

이렇게하면 O(MN)인가?

 

사실 이러면 이진탐색이고 뭐고 점의 좌표 10,30,50을 차례대로 순회해서,

 

각 점이 1이상 5이하인지 검사하면 되잖아

 

하지만 M,N은 최악이 10만이라 당연히 O(MN)은 안되겠지

 

-------------------------------------------------------------------

 

다른 방법으로 이분탐색을 한다면.. 1을 start로 하고 5를 end로 해서

 

점의 좌표 10,30,50,...을 차례대로 순회한다음에 이를 target으로 잡은 다음에

 

이분탐색을 한다면...

 

아니 이게 O(MNlogN)인가??? .. 더 이상한데??

 

이럴거면 그냥 위에 했던대로 이분탐색이 필요없고 10이 1이상 5이하인지, 30이 1이상 5이하인지,... 부등식으로 바로 되는데..

 

-------------------------------------------------------------------

 

이러면 반대로 생각해보자

 

10,30,50,... 점의 좌표가 array이고, 선분의 시작점과 끝점인

 

1 5 

 

5 21 

 

22 59

 

210 293...

 

얘들을 lower bound와 upper bound로 각각 찾는다면?

 

array에서 1에 대한 lower bound와 5에 대한 upper bound를 찾아서 두 지점의 차이를 구한다면..

 

그것이 1과 5 사이에 들어있는 점의 좌표의 개수와 같잖아

 

lower bound, upper bound가 O(logN)이므로 O(MlogN)으로 빠르게 가능하겠다

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static int lowerBound(int[] arr, int target, int start, int end){

        while (start < end){
            int mid = start + (end - start)/2;

            if(arr[mid] >= target){
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }

    public static int upperBound(int[] arr, int target, int start, int end){

        while (start < end){

            int mid = start + (end - start)/2;

            if(arr[mid] > target){
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return end - 1;
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr);

        for(int i = 0; i < m; i++){

            int target1 = sc.nextInt();
            int target2 = sc.nextInt();

            int lower = lowerBound(arr,target1,0,n);
            int upper = upperBound(arr,target2,0,n);

            if (lower == n || upper == -1){
                System.out.println(0);
            } else {
                System.out.println((upper+1)-lower);
            }
        }

    }
}

 

처음에 lower가 n인 경우만 선분에 들어간 점의 개수가 없다라고 생각했지만

 

upper가 -1인 경우에도 선분에 들어간 점의 개수가 없다..

 

그리고 당연하지만, 이분탐색을 하기전에 array는 정렬해야한다

 

 

3. 문제2

 

n명의 사람과 컴퓨터가 함께하는 특별한 숫자 게임을 진행해보려고 합니다.
이 게임에서는 먼저 컴퓨터가 1이상 m이하의 수 중 하나를 선택합니다. 처음으로 사람 A가 그 숫자를 예측하고, 컴퓨터는 사람이 예측한 숫자가 자신이 선택한 숫자보다 작은지, 같은지 혹은 큰지를 얘기해줍니다. 예측한 숫자가 작거나 더 클 경우 그 다음 사람 턴으로 넘어가며, 같은 경우 그 사람이 벌칙을 받게 됩니다. 이 게임에서 사람들은 원형으로 앉아 있기 때문에 게임이 끝날 때까지 그 다음 사람이 게임을 계속합니다. 또, 모두가 게임을 빨리 끝내고 싶어하기 때문에 답이 될 수 있는 범위 중 항상 가운데 값을 고릅니다. (범위의 양 끝이 L, R이라 한다면 가운데 값은 ⌊2L+R​⌋로 정의됩니다)

컴퓨터가 처음 a이상 b이하인 수 만을 선택한다 했을 때, 게임이 가장 적게 지속될 때와 가장 오래 지속 될 때를 계산하는 프로그램을 작성해보세요.

 

첫 번째 줄에는 m이 주어집니다.

두 번째 줄에는 a와 b가 공백을 사이에 두고 주어집니다.

• 1 ≤ m ≤ 10^18
• 1 ≤ a ≤ b ≤ m (단, b - a ≤ 10^5)

 

4. 풀이

 

문제를 보면 일단 1이상 m이하의 수 중에서 이분탐색을 해서 숫자를 맞히는 과정을 하는데.. 몇번만에 맞추는지 구해야할 것 같은데

 

컴퓨터가 a이상 b이하의 수만을 선택하는데.. 가장 적게 지속되는 경우와 가장 오래 지속되는 경우를 구하래..

 

여기서 사고가 멈췄는데

 

그럴 필요가 없다

 

컴퓨터는 기본이 완전탐색이다. 

 

a이상 b이하의 수를 모두 검사해서 가장 적게 이분탐색하는 경우와 가장 많이 이분탐색하는 경우를 해보면 되잖아

 

여기서 이분탐색하는 범위는 a이상 b이하가 아니라.. 당연히 1이상 m이하이다 

 

a부터 a+1, a+2, ... , b까지 각각을 target으로 삼아서 1이상 m이하에서 이분 탐색을 한다고 할때,

 

몇번만에 가능한지 턴 수를 세서 return

 

import java.util.Scanner;

public class Main {
    public static long binarySearch(long target,long start,long end){


        long turn = 0;

        while(start <= end){
            turn += 1;

            long mid = start + (end - start)/2;


            if(mid > target){
                end = mid - 1;
            } else if(mid < target){
                start = mid + 1;
            } else {

                return turn;
            }
        }

        return -1;
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        long m = sc.nextLong();

        long a = sc.nextLong();
        long b = sc.nextLong();

        long max = 0;
        long min = 1000000001;

        for(long i = a; i <= b; i++){
            long turn = binarySearch(i,1,m);

            if(max < turn){
                max = turn;
            }

            if(min > turn){
                min = turn;
            }
        }
        System.out.print(min + " " + max);
    }
}

 

이번에는 삼분탐색 형태로 mid > target인 경우, mid < target인 경우, mid == target인 경우로 나눠서 해봤다

 

반드시 범위 안에 target이 존재하니까..

 

그리고 이렇게 구현한다면 start < end가 아니라, start <= end여야 정확히 턴 수를 셀 수 있다

 

그러니까 start < end이면...

 

target = 6일때,

 

start = 4

 

mid = 5

 

end = 6에서...

 

mid, target 검사를 하고, 5 < 6이면.. start = mid + 1 = 6이 될텐데, 그러면 start < end인지 검사할때,

 

start = end니까 반복문을 탈출해서, turn을 정확히 return하지 못한다

 

-----------------------------------------------------------------------------------------------------------------------

 

그리고 자바는 type이 중요하다보니.. m의 범위가 10의 18제곱이라 int가 10의 9제곱까지만 커버하다보니 

 

long으로 선언해야한다는 점

 

----------------------------------------------------------------------------------------------------------------------

 

자바 함수도 return의 type 선언이 중요한데... 아니 파이썬과는 다르게.. 

 

return이 절대로 안될 것이라고 생각되는 지점에도 return을 반드시 써야하더라고

 

아래 함수에서 return -1;을 하지 않으면 에러가 나더라

 

    public static long binarySearch(long target,long start,long end){


        long turn = 0;

        while(start <= end){
            turn += 1;

            long mid = start + (end - start)/2;


            if(mid > target){
                end = mid - 1;
            } else if(mid < target){
                start = mid + 1;
            } else {

                return turn;
            }
        }
        //여기를 쓰지 않으면 에러가 남...
        return -1;
    }