[java 백준] 실버 4/10816번 숫자카드 2

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

10816번: 숫자 카드 2

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int n;
    public static int m;
 
    public static int lower(int target, int[] arr) {
        int start = 0;
        int end = arr.length;
        while (start < end) {
            int mid = (start + end) / 2;
            if (target <= arr[mid]) {
                end = mid;
                // 하한선을 내려줘서 target 왼쪽 값들 중
                // target 이상인 것들 중 가장 작은 인덱스 탐색
            } else {
                start = mid + 1;
            }
 
        }
        return end;
 
    }
 
    public static int upper(int target, int[] arr) {
        int start = 0;
        int end = arr.length;
        while (start < end) {
            int mid = (start + end) / 2;
 
            if (target < arr[mid]) {
                end = mid; // 하한선을 내려줘서 target 왼쪽 값들 중
                // target을 초과하는 값들 중 가장 작은 값/인덱스 찾아주기
            } else {
                start = mid + 1;
            }
        }
        return end;
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[] arr = new int[n];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr);
 
        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            int low = lower(target, arr);
            int high = upper(target, arr);
            sb.append(high - low).append(" ");
 
        }
        System.out.println(sb.toString());
 
    }
 
}

 

이 문제는 upper bound와 lower bound를 구현해서 푸는 문제이다.

그래야 시간초과 되지 않고 잘 풀어낼 수 있다. 

 

upper bound와 lower bound

 

숫자카드 배열이 10개 있다.

여기서 우리가 찾고자하는 target값이 3일때 3의 upper bound인덱스와 lower bound 인덱스를 찾아보자.

인덱스가 1부터 시작할때 lower bound는 2이다. lower bound는 우리가 찾고자하는 값(target)이 처음나오는 위치를 말한다.

 

반대로 upper bound는 우리가 찾고자하는 값보다 큰 값이 처음 나오는 위치를 말한다.

target값인 3의 upper bound는 4이다. 

 

이걸 코드로 구현하면

 

    public static int lower(int target, int[] arr) {
        int start = 0;
        int end = arr.length;
        while (start < end) {
            int mid = (start + end) / 2;
            if (target <= arr[mid]) {
                end = mid;
                // 하한선을 내려줘서 target 왼쪽 값들 중
                // target 이상인 것들 중 가장 작은 인덱스 탐색
            } else {
                start = mid + 1;
            }
 
        }
        return end;
 
    }
 
    public static int upper(int target, int[] arr) {
        int start = 0;
        int end = arr.length;
        while (start < end) {
            int mid = (start + end) / 2;
 
            if (target < arr[mid]) {
                end = mid; // 하한선을 내려줘서 target 왼쪽 값들 중
                // target을 초과하는 값들 중 가장 작은 값/인덱스 찾아주기
            } else {
                start = mid + 1;
            }
        }
        return end;
 
    }

lower는 찾고자하는 값보다 같거나 큰 값들을 찾아주는 것이기에 등호가 붙는다.

target<=arr[mid] 

 

이때 end=mid 즉 끝값을 중간값으로 설정해서 중간값보다 왼쪽값을 탐색해준다.

이는 taget보다 크거나 같은 값들 중 가장 작은 인덱스를 찾기 위함이다. 

 

upper는 찾고자 하는 값보다 큰 값들을 찾아주는 것이기에 부등호만 붙는다.

target<arr[mid]

 

이때 end=mid 즉 끝값을 중간값으로 설정해서 중간값보다 왼쪽값을 탐색해준다.

이는 target보다 큰 값들 중 가장 작은 인덱스를 찾기 위함이다. 

 

 

여기서 좀만 더 생각해 보면

결국 중복원소 길이는 upper bound - lower bound를 해준 것으로 생각해볼 수 있다.

target이 3일 때도 upper bound 인덱스는 4 lower bound 인덱스는 2 인데  원소가 3인 애가 2개 있으니까

중복원소의 길이는 2이고, 이 값은 upper bound(4) - lower bound (2) 와 일치하는 것을 알 수 있다. 

 

 

 

기본 이분탐색과의 비교 

 

1) 충분할 때  --> 등호포함

target>=arr[mid]

즉 찾고자 하는 값이 중간값보다 크거나 같으면

start=mid+1 로 하한선을 높여준다.

 

2) 부족할 때 -> 등호포함 x

target<arr[mid]

찾고자 하는 값이 중간값보다 작으면

end=mid-1로 하한선을 낮게 해준다.

 

근데 upper bound나 lower bound 는 신기하게도 end=mid만 해준다.

 

그 이유는 예제를 통해 설명하겠다. (upper bound만 설명해보겠다)

숫자카드 배열이 7개 있고, target 값이 3이다. target값의 upper bound를 찾아보자.

 

start=0, end =7 mid=3

 

3<5(arr[mid]) 이기에 end=mid 즉 end=3이다.

왜냐하면 upper bound는 찾고자하는 값보다 처음으로 큰 값이 나올때의 인덱스이기 때문에 

굳이 end-1하지 않아도 end=3이 upper bound가 될 수 있기 때문이다.

실제로도 3번째 인덱스가 3의 upperbound 이다. 3-1만 해줘도 바로 컷된다.

 

주의해야 할 것!(등호와 관련하여) 

while (start < end)에서 왜 등호가 안붙는지 궁금했다. 다른 이진탐색은 while(start<=end) 여도 잘 돌아가는데 얘는 등호를 썼을때 에러가 뜬다.

 

예를 들어 while(start<=end) 일때로 가정하고 문제를 풀어보자. 

 

7개의 숫자 배열 중 찾고자 하는 값(target 값)이 3일 때, 이 3의 lower bound를 구하는 과정을 상세히 알아보자.

 

start=0,end =7일 때

mid=3 그러므로 target<=5(arr[mid]) end=3

 

start=0 end=3 일때

mid는 1 그러므로 target<=3(arr[mid]) end=1

 

start =0 end =1  일 때

mid=1 그러므로 target> 1(arr[mid])  start=1

 

start=1 end=1일때

mid =1 그러므로 target>=arr[mid]  end=1

--> end=mid-1이 아닌 end=mid 를 해줬기에 무한루프를 계속 돌거다

그래서 등호 빼줘야 한다. 

 

 

++) 그리고 end값은 배열에 (n-1)번째 인덱스까지만 원소를 넣었다고 end=n-1로 해주면 안된다. 알고보니 탐색범위가 start이상 end미만 이여서 end가 원래 인덱스보다 1만큼 크게 설정해줘야한다. 

결론적으로 end=arr.length라고 처음에 선언해주면 문제없이 돌아간다. 

 

 

솔직히 과정을 손으로 써가면서 얼추 이렇구나 이해하긴 했는데 아직까진 완벽히 이해하진 못했다. 시간이 들것같다. 

 

참고자료

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

https://yhwan.tistory.com/10

[백준] 10816번: 숫자 카드 2 - C++

 

 

https://blog.naver.com/bestmaker0290/220820005454

알고리즘 기초 - Lower Bound & Upper Bound