10816번: 숫자 카드 2 [JAVA]

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

10816번: 숫자 카드 2

 

 

일단 풀 수 있는대로 풀다가 시간초과 먼저 나서, 찾아보니

HashMap을 이용한 풀이도 있었지만 일단 이분 탐색을 공부하고 있어서 이분 탐색 사용해서 풀고 싶었다.

중복 원소의 개수를 알아내기 위해, 중복 원소의 왼쪽 끝 index과 오른쪽 끝 index을 알아내야 한다.

 

lower bound랑 upper bound 개념에 대해 먼저 알아둬야 한다고 해서, 블로그에 정리된 글을 공부하고 왔다.

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

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

 

 

접근 방식) 

-이분 탐색을 사용해서 배열을 돌다가, 해당 key를 발견하면 중복 값이 있는지 좌우를 확인하려고 했음 → 시간초과

그래서 upper bound와 lower bound에 대해 위의 블로그에서 공부했다.

✔ upper bound(상한): 찾는 값 초과하는 첫 위치를 반환

✔ lower bound(하한): 찾는 값 이상인 첫 위치를 반환

 

1) 이분탐색(중복값의 상한선과 하한선을 사용)

2) hashmap 사용

풀어봤다.

+) 시간초과 났던 내 코드 ㅎvㅎ

 

1) 이분탐색(upper bound, lower bound 개념)

package tony_git.binary_search;

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

public class B_10816_binarySearch {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        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);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            // 중복 원소 개수 count (상한선 - 하한선)
            sb.append(upperBound(key) - lowerBound(key)).append(' ');
        }
        System.out.println(sb);
    }

    static int lowerBound(int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            /*
            * 중복되는 값의 하한(이상)선을 찾아야 하는 상황
            * key가 mid보다 작거나 같다면,
            * right 값을 mid - 1로 바꿔줘야 함
            * */
            if (key <= arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }

    static int upperBound(int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            /*
            * 중복되는 값의 상한선(초과)을 찾아야 하는 상황
            * key가 mid보다 작다면,
            * right 값을 mid - 1로 바꿔줘야 함
            * */
            if (key < arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left;
    }
}

 

2) hashmap 

package tony_git.binary_search;

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

public class B_10816_hashMap {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> cards = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int key = Integer.parseInt(st.nextToken());
            cards.put(key, cards.getOrDefault(key, 0) + 1);
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(cards.getOrDefault(key, 0)).append(' ');
        }
        System.out.println(sb);
    }
}

 

 

+) 시간초과 났던 거

좌우로 같은 숫자가 없는지 반복문으로 각각 돌면서 체크하려고 했다.

시간초과가 날 거 같았지만 다른 방법으로는 어떻게 해야할 지 몰라서, 일단 구현했지만 역시나 시간초과 ㅋㅋㅋㅋㅋㅋ

package tony_git.binary_search;

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

public class B_10816 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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);

        int M = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int find = Integer.parseInt(st.nextToken());
            int left = 0;
            int right = N - 1;
            int count = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (arr[mid] == find) {
                    count++;
                    // 좌우로 같은 숫자 없는지 체크해야함
                    int checkLeft = mid - 1;
                    for (int k = checkLeft; k >= 0; k--) {
                        if (arr[k] == find)
                            count++;
                        else
                            break;
                    }

                    int checkRight = mid + 1;
                    for (int k = checkRight; k < N; k++) {
                        if (arr[k] == find)
                            count++;
                        else
                            break;
                    }
                    break;
                } else if (arr[mid] < find) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            sb.append(count).append(' ');
        }
        System.out.println(sb);
    }
}