백준 - 집합과 맵 10816번 숫자 카드2 / 이분 탐색을 활용 ( 중복값 )

= 내가 접근한 방법 = 

숫자 카드1 문제랑 똑같이 접근했다.

 

Map을 이용해서 Map의 메서드 getOrDefault를 활용하는 방식으로 해결했는데 이 문제도 이분 탐색을 이용해서 풀어야 되는 문제였다.

 

지난 숫자 카드1보다는 조금 더 간결하게 코드를 짜긴 했지만, 결국 이분 탐색이 핵심이다.

getOrDefault라는 메서드는 card라는 맵 안에 내가 입력한 값이 있으면 그 key의 밸류를 갖고오는 것이고

없으면 defaultValue ( 내가 지정한 값 ) 0을 넣는 메서드다.

 

이 메서드를 활용하면 이분 탐색을 안 하고 쉽게 해결할 수 있다.

 

= 이분 탐색 =

https://st-lab.tistory.com/267 이 블로그를 참고해서 공부했다.

나보다 훨씬 자세한 설명은 이 블로그에 있다.

 

간단하게 말하면 내가 원하는 값을 찾았을 때, 

즉 arr[mid] == target일 때, 그 때 target의 시작 값, 끝 값의 위치를 찾으면 된다.

 

이 중복을 찾는다는 알고리즘은 되게 어려웠다. 사실 지금도 계속 노트에 쓰면서 이럴 때~ 이럴 때 ~게 되는 구나 하면서 공부를 했지만.... 솔직히 다른 사람의 풀이를 보지 않았다면 스스로 해결을 못했을 것 같다.

 

물론 이론으로는 되게 간단한데, 이걸 코드로 짠다는게 정말 어렵다.

 

1 2 2 4 5 6 7 8 9 10이라는 10개의 숫자가 있다고 가정하자.

 

숫자 카드1과 다르게 이번에 end값은 length - 1로 안 잡았따

이거에 대한 이유는 설명을 못하겠다.. 완전 이해를 기반으로 해결했다기보다는 아 이렇게 알고리즘을 짤 수 있구나 라고 이해를 했기때문에 스스로 공부가 더 필요한 부분이다.

 

하한선과 상한선을 구하면 된다.

target = 2일 때, 2의 시작 index와 2가 끝나는 index

low = 1, hi = 3을 구해서 hi - low를 하면 2 => 2라는 숫자는 배열 안에서 2개 존재한다.

 

1. 하한선을 구하는 메서드

 

1 2 2 4 5 6 7 8 9 10 이라는 배열과

key값이 2일 때를 가정하자

 

lo = 0, hi = 10

mid = 5

 

key값이 arr[5] ( 6 )보다 작으므로 hi = mid의 값으로 바꿔줌

key 값과 arr[mid]값이 같으므로 이런식으로 쭉 진행하면 된다.

 

low일 때, 2라는 숫자가 시작하는 index를 구하고

up일 때, 2라는 숫자가 끝나고 다른 숫자가 시작하는 index를 구하는 과정임!

 

 

= 최종 코드 =

 

package 집합과_맵.silver.숫자카드2_no10816;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class ReMain {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());

        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);
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int key = Integer.parseInt(st.nextToken());

            sb.append(upperBound(arr, key) - low(arr, key)).append(" ");
        }

        System.out.println(sb);

    }

    public static int low(int[] arr, int key) {
        int lo = 0;
        int hi = arr.length;

        while (lo < hi) {
            int mid = (lo + hi) / 2;

            if (key <= arr[mid]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo;
    }

    static int upperBound(int[] arr, int key) {
        int lo = 0;
        int hi = arr.length;

        // lo가 hi랑 같아질 때 까지 반복
        while (lo < hi) {

            int mid = (lo + hi) / 2; // 중간위치를 구한다.

            // key값이 중간 위치의 값보다 작을 경우
            if (key < arr[mid]) {
                hi = mid;
            }
            // 중복원소의 경우 else에서 처리된다.
            else {
                lo = mid + 1;
            }

        }

        return lo;
    }
}