[BOJ 10816번] 숫자 카드 2 (JAVA)

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

10816번: 숫자 카드 2

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

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
	   int N=Integer.parseInt(br.readLine());
	   int arr[]=new int[20000001];
	   String s[]=br.readLine().split(" ");
	   for(int i=0;i<N;i++) {
		   arr[Integer.parseInt(s[i])+10000000]++;
	   }
	   int M=Integer.parseInt(br.readLine());
	   String s1[]=br.readLine().split(" ");
	   for(int i=0;i<M;i++) {
		  sb.append(arr[Integer.parseInt(s1[i])+10000000]+" ");
	   }
	   System.out.println(sb);
	}
}

처음에는 아래와 같이 이분 탐색을 이용해서 접근했습니다.

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

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
	   int N=Integer.parseInt(br.readLine());
	   int arr[]=new int[N];
	   String s[]=br.readLine().split(" ");
	   for(int i=0;i<N;i++) {
		   arr[i]=Integer.parseInt(s[i]);
	   }
	   int M=Integer.parseInt(br.readLine());
	   String s1[]=br.readLine().split(" ");
	   int arr2[]=new int[M];
	   int arr_cnt[]=new int[M];
	   for(int i=0;i<M;i++) {
		  arr2[i]=Integer.parseInt(s1[i]);
	   }
	   Arrays.sort(arr);
//	   for(int i=0;i<N;i++) System.out.print(arr[i]+" ");
//	   System.out.println();
//	   for(int i=0;i<M;i++) System.out.print(arr2[i]+" ");
//	   System.out.println();
	   
	   for(int i=0;i<M;i++) {
		   int left=0, right=N-1;
		   while(left<=right) {
			   int mid=(left+right)/2;
			   if(arr[mid]>arr2[i])	right=mid-1;
			   else if(arr[mid]<arr2[i]) left=mid+1;
			   else {
				   arr_cnt[i]++;
				   for(int j=1;;j++) {
					   if(mid+j>=N) break;
					   if(arr[mid+j]==arr2[i])	{
						   arr_cnt[i]++;
					   }
					   else {
						   break;
					   }
				   }
				   for(int j=1;;j++) {
					   if(mid-j<0) break;
					   if(arr[mid-j]==arr2[i]) arr_cnt[i]++;
					   else break;
				   }
				   break;
			   }
		   }
	   }
	   for(int i=0;i<M;i++) {
		   sb.append(arr_cnt[i]+" ");
	   }
	   System.out.println(sb);
	}
}

 

정렬한 후, 이분 탐색 방법을 이용해서 값을 찾는데요, 이 때 같은 값이 있을 수도 있으므로 찾은 값의 인덱스에서 +1씩, -1씩 각각 해주면서 같은 값이 몇 개 있는지 찾아서 arr_cnt 배열에 저장했습니다.

이 방법을 사용하면 테스트 케이스는 실행되나 시간 초과가 발생했습니다.

그래서 해결책을 찾아보니 맨 위의 방법처럼 배열을 사용해서 푸는 방법이 있었습니다.

-10,000,000부터 10,000,000까지의 숫자를 사용할 수 있으므로 크기가 20,000,001인 배열을 만들고, 숫자 값을 입력받아 그 숫자+10,000,000번째 인덱스의 배열의 값을 +1해줍니다.

예를 들어 숫자 10 10 -2 10 을 입력받았다고 하면,

arr[10,000,010]=3, arr[9,999,998]=1이고 나머지 값은 0이 됩니다.

이렇게 되면 각 숫자별로 몇 개 씩 가지고 있는지 알 수 있는데요, 이후, M 개의 숫자를 받아 그 숫자+10,000,000번째 arr 배열의 값을 출력해주면 됩니다.