[BAEKJOON] - 10816번 : 숫자 카드2

10816번 문제 링크

⌛ 시간 복잡도

• 1초 / N 500,000 / M 500,000
• O(N^2)은 시간 초과이므로, O(NlogN) 이하의 알고리즘으로 구현해줘야 합니다.

📜 로직

• 기존의 이분 탐색 알고리즘을 이용하며, 시작 index를 앞과 뒤를 구분하여 두 index의 차이만큼 출력해주면, target 데이터의 갯수가 출력됩니다.
• 하지만, 다른 사용자의 풀이를 확인하던 중 '계수 정렬'을 이용한 O(n)의 알고리즘을 참고하여 구현해봤습니다.

"계수정렬" 은 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방식입니다. 배열 내 데이터가 몇 번 또는 등장 여부를 확인하여 배열에 표시할 수 있고, 데이터 범위가 정해져 있는 경우(자바에서는 배열의 최대 길이가 int 범위를 넘지 못하며 메모리 낭비가 심하다)에 위 정렬 방식을 사용할 수 있습니다.

우선, 숫자 카드에 적힌 수의 최대 범위는 -10,000,000 ~ 10,000,000 입니다. 하지만, 음수를 배열 index로 표현할 수 없기 때문에, offset을 20,000,000 범위로 확장하여 구현하면 됩니다.

1. int 배열을 20,000,001 크기로 선언해줍니다.(index는 0부터 인것을 감안)
2. N번의 루프를 돌려 요소를 index로 하는 int 배열에 카운팅(계수)을 해줍니다.
3. M번의 루프를 돌려 요소를 index로 받아 int 배열에서 카운팅 횟수를 조회하여 출력하도록 구현해줍니다.

🥹 성공

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());
        
        int[] a = new int[20000001];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<n; i++){
            int k = Integer.parseInt(st.nextToken());
            a[10000000 + k]++;
        }
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        br.close();
        
        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());
            
            sb.append(a[target + 10000000]).append(" ");
        }
        
        sb.deleteCharAt(sb.length() - 1);
        
        System.out.println(sb);
    }
}

lower_bound & upper_bound

lower_bound & uppser_bound 개념 정리

기본적인 개념은 위 링크에 다른 분의 포스팅을 참조하여 정리한 글이 있으니 참고 바랍니다.

추가적으로 위 방식으로 구현해보려고 합니다. 기존에는 카운팅 정렬을 통해서 구현했지만, lower_bound & upper_bound로 구현하는 방식도 종종 사용되므로 이해하고 구현 연습을 해보는 것이 좋을 것 같습니다.

핵심 로직은 아래 그림과 같습니다.

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

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

😀 구현

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());
        
        int[] a = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for(int i=0; i <n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        // 이분탐색을 위해서는 정렬이 선행되어야 함.
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        
        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());
            
            sb.append(upper_bound(a,target) - lower_bound(a,target)).append(" ");
        }
        
        sb.deleteCharAt(sb.length() - 1);
        
        System.out.println(sb);
    }
    
    static int lower_bound(int[] arr, int target){
        int lo = 0;
        int hi = arr.length ;
        
        while(lo < hi){
        // int 범위 초과인 경우, mid 값이 음수가 나올 수 있기 때문.
            int mid = lo + (hi - lo) / 2;
            
            // 동일 요소에 대해 좌측셋으로 유도하기 위해 이하의 값으로 제한.
            if(target <= arr[mid]){
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }

        return lo;
    }
    
    static int upper_bound(int[] arr, int target){
        int lo = 0;
        int hi = arr.length ;
        
        while(lo < hi){
            int mid = lo + (hi - lo) / 2;
            
            if(target < arr[mid]){
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}