99클럽 코테 스터디 14일차 TIL + 오늘의 학습 키워드

오늘의 학습내용

• 정렬된 HashMap : TreeMap
• 이분탐색

공부한 내용

1. hashmap의 키를 정렬된 형태로 가지고 싶은 경우 treemap을 이용하면 된다.
2. 시간초과를 고려한다면 이중 반복문보다 정렬 후 이분탐색을 진행하면 된다.

오늘의 회고

이전에 해결했던 숫자카드 문제와 동일하게 접근하였다.

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

나의 풀이

1. 상근이가 가지고 있는 숫자카드를 HashMap의 key로 두고 반복되는 개수만큼 그 value 값으로 지정한다.
2. 상근이의 key를 대상으로 이분탐색을 하기 위해서는 HashMap의 키 자체에서 정렬이 되어야 하는데 HashMap의 키를 정렬하려면 Keyset()을 대상으로 TreeMap을 구상한다.
3. TreeMap의 Key의 최솟값과 최댓값을 이분탐색의 low 와 high로 지정하면 O(log n)의 복잡도로 테스트케이스에 있는 숫자를 상근이가 얼만큼 가지고 있는지 구할 수 있다.

package baekjoon.이분탐색;

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

public class 숫자_카드2 {
    private static int[] cards, test;
    private static HashMap<Integer, Integer> cardMap;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); //상근이 가지고 있는 숫자카드 개수
        cards = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            cards[i] = Integer.parseInt(st.nextToken());
        }
        int M = Integer.parseInt(br.readLine()); //테슽트할 숫자 카드 개수
        test = new int[M];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++){
            test[i] = Integer.parseInt(st.nextToken());
        }
        cardMap = new HashMap<>();
        for(int i=0; i<N; i++){
            if(cardMap.containsKey(cards[i])){
                int value = cardMap.get(cards[i]);
                cardMap.replace(cards[i], value+1);
            }else{
                cardMap.put(cards[i], 1);
            }
        }
        StringBuilder sb = new StringBuilder();
        Set<Integer> keys = cardMap.keySet();
        TreeSet<Integer> sortedKeys = new TreeSet<>(keys);
        int minKey = sortedKeys.first();
        int maxKey = sortedKeys.last();
        for(int i=0; i<M; i++){
            sb.append(binarySearch(test[i], minKey, maxKey)).append(" ");
        }
        System.out.print(sb);
    }
    public static int binarySearch(int key, int low, int high){
        int mid;

        while(low <= high){
            mid = (low + high)/2;
            if(key == mid){
                if(cardMap.containsKey(key)){
                    return cardMap.get(mid);
                }
                break;
            }else if(key < mid){
                high = mid-1;
            }else{
                low = mid+1;
            }
        }
        return 0;
    }
}