[BOJ 길라잡이/Java] 8일차 #10816 숫자 카드 2

알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색

- 해시를 사용한 집합과 맵

 

일단 내가 푼 방법은 HashMap이다.

N개 주어진 숫자 카드 각각 몇 개 있는지를 알아야 하기 때문이다.

 

HashMap 사용

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            int cnt = map.getOrDefault(num, 0);
            cnt++;
            map.put(num, cnt);
        }

        StringBuilder sb = new StringBuilder();
        int M = Integer.parseInt(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int ansNum = Integer.parseInt(st2.nextToken());
            sb.append(map.getOrDefault(ansNum, 0) + " ");
        }

        System.out.println(sb.toString());
    }
}

 

근데 처음에는 귀찮아서 StringBuilder 안쓰고 그대로 print로 출력했는데

시간제한에 걸렸다. 웬만해서는 StringBuilder 쓰는게 나을듯..

 

이진탐색 사용

찾아보니 이진탐색으로 푼 사람이 많은 것 같았다.

따라서 이 방법도 공부해봤다.

 

원래 이진탐색은 값이 일치하면 true or false를 리턴하는 구조였다.

(중앙값과 찾고자 하는 값)

그러나 이번 문제는 연속으로 중복된 값이 몇 번 입력됐는지 찾아야 하기 때문에

찾고자 하는 값의 인덱스 범위를 구해야 한다.

 

이때 lower_bound와 upper_bound의 개념을 사용한다.

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

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

            sb.append(upperBound(arr, num) - lowerBound(arr, num)).append(" ");
        }

        System.out.println(sb.toString());
    }
    static int lowerBound(int[] arr, int num) {
            int left = 0;
            int right = arr.length;

            while (left < right) {
                int mid = (left + right) / 2;
                if (num <= arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }

        static int upperBound(int[] arr, int num) {
            int left = 0;
            int right = arr.length;

            while (left < right) {
                int mid = (left + right) / 2;
                if (num < arr[mid]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
}