[JAVA] 입력 받은 숫자의 개수 구하기(정렬, 이분 탐색, HashMap, TreeMap)

백준 10816번 문제 '숫자 카드 2'
https://www.acmicpc.net/problem/10816

개요

중복 가능한 숫자 카드 N개를 입력받고, M개의 임의의 정수를 입력해, 해당 정수가 각각 몇 개 있는지 구한다.

접근

public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //1번
        List<String> list = new ArrayList<>();
        int testCase = Integer.parseInt(br.readLine());
        String inputNum [] = br.readLine().split(" ");
        for(String i : inputNum){
            list.add(i);
        }

        //2번
        int findNumbers = Integer.parseInt(br.readLine());
        String findNum [] = br.readLine().split(" ");

        //3번
        for(String i : findNum){
            int count = Collections.frequency(list, i);
            bw.write(count + " ");
        }
        bw.flush();
        bw.close();
    }

1.ArrayList에 N개의 카드를 저장해 놓는다.
2.findNum배열에 M개의 타겟 숫자를 입력받는다.
3.findNum(타겟 숫자 배열)을 처음부터 끝까지 탐색하여, list에 몇 개가 저장되어 있는지 Collections.frequency()로 구한다.
4.BufferedWriter 클래스 메소드인 write()로 저장 후, flush()로 한번에 출력.

 

결과

시간 초과

내가 작성한 코드는 ArrayList를 이용한 선형 탐색(Brute Force Search)방식이다. 처음부터 끝까지 순회하기 때문에 시간 초과가 발생한 것.
Collections.frequency(list, i)를 사용했는데, 이 함수는 리스트를 처음부터 끝까지 순회하면서 특정 원소(i)가 몇 번 등장했는지 세는 방식이다.
따라서, O(N) 시간이 걸리고, 이를 M번 반복하면 O(NM)이 되어 시간 초과가 발생한 것이다.

 

개선 방법

3가지가 있다.

1. HashMap

입력 크기가 크고, 빠른 검색이 필요할 때.

시간 복잡도 : O(N + M)

단점 : 메모리를 더 사용함.

2. TreeMap

숫자를 정렬된 상태로 유지하고 싶을 때.

시간 복잡도 : O(NlogN + MlogM)

단점 : HashMap보다 느림.

3. 정렬 후, 이분 탐색

추가적인 메모리를 줄이고 싶을 때.

시간 복잡도 : O(NlogN + MlogM)

단점 : 구현이 복잡함.

HashMap으로 구현한 경우

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        String [] inputNum = br.readLine().split(" ");

        // n개의 숫자를 저장할 HashMap
        Map<String, Integer> map = new HashMap<>();
        for(String num : inputNum){
            //Map에 num이 key로 이미 존재하면, 해당하는 num의 value을 반환해 +1한 후 value 갱신.
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        int m = Integer.parseInt(br.readLine());
        String [] findNum = br.readLine().split(" ");

        //타겟 숫자에 해당하는 key가 있으면 대응하는 value(개수) 출력. 없을 경우 defaultValue인 0 출력.
        for(String num : findNum){
            bw.write(map.getOrDefault(num, 0) + " ");
        }
        bw.flush();
        bw.close();
    }
}

 

.getOrDefault(key, defaultValue) : map에 해당 key가 이미 존재하면, 대응하는 value값을 반환한다. 없거나 null인 경우 설정해 놓은 defaultValue를 반환한다.

 

📌 HashMap이 추가로 사용하는 메모리

1. 키(Key)와 값(Value)를 저장해야 함
   • HashMap은 입력 숫자(키)와 등장 횟수(값) 를 저장하는 추가적인 메모리를 사용한다.
   • 예를 들어, N = 500,000개의 숫자가 모두 다르면, 500,000개의 키-값 쌍을 저장해야 한다.
2. 해시 테이블(배열)과 해시 충돌 처리 비용
   • HashMap은 내부적으로 해시 테이블(배열) 을 사용하며, 이를 위한 버킷(배열 크기) 을 관리한다.
   • 해시 충돌이 발생하면 추가적인 연결 리스트(또는 트리 구조) 가 필요할 수도 있다.

 

TreeMap으로 구현한 경우

상단의 코드에서

Map<String, Integer> map = new TreeMap<>();

로 바뀌는 것 외엔 변동 사항 없음.

TreeMap은 자동 정렬이 되기 때문에 정렬된 상태에서 검색할 수 있는 장점이 있다.

 

정렬 후 이분 탐색

*이분탐색은 정렬된 배열에서만 동작한다.

• 만약 배열이 정렬되지 않았다면, 중간값(mid)을 기준으로 왼쪽이 작고 오른쪽이 크다는 보장이 없음.
• 그러면 탐색 범위를 줄일 방법이 없어지므로, 이분 탐색 자체가 성립하지 않게 된다.

핵심 코드

lowerBound(int n) : 배열에서 n(타겟 숫자)가 처음 등장하는 위치(인덱스)를 찾는다.

upperBound(int n) : 배열에서 n(타겟 숫자)보다 큰 값이 처음 등장하는 위치(n이 아닌 다음 숫자가 나오는 위치)를 찾음.

-> upperBound - lowerBound = n(타겟 숫자)의 개수.

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        //카드의 숫자를 저장할 배열 arr
        int[] arr = new int[N];
        int i = 0;
        String [] inputNum = br.readLine().split(" ");
        for(String n : inputNum){
            arr[i++] = Integer.parseInt(n);
        }
        //정렬 시간 복잡도 : O(NlogN)
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        String [] targetNum = br.readLine().split(" ");
        for(int j = 0; j < M; j++){
            //해당 타겟 숫자의 개수를 구하고 출력 대기.
            bw.write(upperBound(arr, Integer.parseInt(targetNum[j])) - lowerBound(arr, Integer.parseInt(targetNum[j])) + " ");
        }
        bw.flush();
        bw.close();
    }
    //lowerBound 구현
    private static int lowerBound(int [] arr, int target){
        int left = 0, right = arr.length;
        while(left < right){
            int mid = (left + right) / 2;
            if(arr[mid] >= target) right = mid;
            else left = mid + 1;
        }
        //target이 처음 등장한 위치 반환
        return left;
    }
    //upperBound 구현
    private static int upperBound(int [] arr, int target){
        int left = 0, right = arr.length;
        while (left < right){
            int mid = (left + right) / 2;
            if(arr[mid] > target) right = mid;
            else left = mid + 1;
        }
        //target보다 큰 값이 나오는 위치 반환
        return left;
    }
}