백준(BOJ) 10816 : 숫자 카드 2 (JAVA)

문제링크 : https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

문제를 보자마자 전형적인 이분탐색문제라고 생각했다. 그렇게 생각하고 문제를 풀었으나, 시간초과...-_- 다른 언어에서도 그런지는 모르겠으나 적어도 자바에서는 이분탐색으로 이 문제를 풀면 시간초과가 뜬다. 이분탐색으로 푼 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cards = new int[n];
        
        for(int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        
        Arrays.sort(cards);
        
        int m = Integer.parseInt(br.readLine());
        
        StringBuffer sb = new StringBuffer();
        st = new StringTokenizer(br.readLine());
        
        for(int i = 0; i < m; i++) {
            int x = Integer.parseInt(st.nextToken());
            int cnt = getCnt(cards, x, n);
            sb.append(cnt + " ");
        }
        
        System.out.println(sb);
    }
 
    private static int getCnt(int[] cards, int x, int n) {
        int left = 0;
        int right = n - 1;
        int cnt = 0;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            
            if(x < cards[mid]) {
                right = mid - 1;
            } else if(x > cards[mid]) {
                left = mid + 1;
            } else {
                cnt = 1;
                int tmp = mid;
                
                while(--tmp >= 0 && cards[tmp] == x) {
                    cnt++;
                }
                
                while(++mid < n && cards[mid] == x) {
                    cnt++;
                }
                
                break;
            }
        }
        
        return cnt;
    }
}

 

그럼 대체 어떻게 풀어야한단 말인가... 고뇌를 하던 와중, 숫자의 범위가 -10,000,000 ~ 10,000,000이라는 게 눈에 들어왔다. 그럼 20,000,001개의 수이고 int 는 4 byte니까 20,000,001 X 4 = 80,000,004 -> 약 80MB~!!!! 생각보다 배열이 크지 않구만~! 배열에 모든 수의 개수를 저장하면 되겠다는 생각이 들었다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] cnt = new int[20_000_001];
        
        for(int i = 0; i < n; i++) {
            cnt[Integer.parseInt(st.nextToken()) + 10_000_000]++;
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < m; i++) {
            sb.append(cnt[Integer.parseInt(st.nextToken()) + 10_000_000] + " ");
        }
        
        System.out.println(sb);
    }
}