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

안녕하세요. 이번에는 백준 10816 숫자 카드 2 문제를 풀어보려고 합니다.

 

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

10816번: 숫자 카드 2

---

Problem

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

사진 1. 문제

---

Solution

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

public class Main {
    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());
        HashMap<Integer, Integer> map = new HashMap<>();
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) + 1);    
        }
        
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            int key = Integer.parseInt(st.nextToken());
            int val = map.getOrDefault(key, 0);
            
            sb.append(val + " ");
        }
        
        System.out.println(sb.toString());
    }
}

 

 이번 문제는 HashMap을 사용해서 문제를 풀면 된다.  Map의 특징은 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. 

 

여기서 핵심은 getOrDefault 기능이다.

/**
*	map에 put(key, value) 를 적는다
*   value에 (map.getOrDefault(key, key값이 없을 시 출력될 기본값)을 적어준다.
*/
map.put(num, map.getOrDefault(num, 0) + 1);

 이렇게 getOrDefault을 사용해서 key값이 반복될 때마다 value을 +1씩 올려주는 방식으로 진행하면 된다.  

 

 이번 문제는 HashMap 말고도 이분 탐색을 사용해서 풀 수 있는 방법도 있었다. st-lab님의 코드를 참고하였다.

이분 탐색

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());
        int[] arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < arr.length; 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());
 
			sb.append(upperBound(arr, key) - lowerBound(arr, key)).append(' ');
		}
        
		System.out.println(sb);
    }
    
    static int upperBound(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 lowerBound(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;
    }
}

---

Performance

1. HashMap

사진 2. 실행 결과

2. 이분 탐색

사진 3. 실행 결과

 

 HashMap 은 O(N)의 시간 복잡도를 갖고 이분 탐색은 O(NlogN)의 시간 복잡도를 갖기 때문에 속도는 살짝 느리긴 하지만 HashMap에 비해 메모리는 적게 드는 것을 확인할 수 있었다. 

---

Reference

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