[백준 10815 : 숫자 카드] [Java]

문제

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

10815번: 숫자 카드

코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<Integer> SK=new ArrayList<Integer>(); //상근이의 카드
		Scanner s=new Scanner(System.in);

		//상근이의 카드를 입력받은 후 오름차순 정렬
		int N=s.nextInt();
		for(int i=0;i<N;i++)
		{
			int n=s.nextInt();
			SK.add(n);
		}
	    Collections.sort(SK); // Arrayist를 오름차순으로 정렬
	    int skcard[]=new int[N];
	    for(int i=0;i<N;i++)
		{
			skcard[i]=SK.get(i); // ArrayList의 원소를 skcard 배열에 넣어줌
		}

	    //구해야 하는 카드 입력받기
	    int M=s.nextInt();
	    int mycard[]=new int[M]; 
	    for(int i=0;i<M;i++)
	    {
	    	int n=s.nextInt();
	    	mycard[i]=n;
	    }

	    //이분탐색을 이용하여 카드 확인하기
	    for(int i=0;i<M;i++) {
	    	int ans=Arrays.binarySearch(skcard, mycard[i]); // 이분탐색
	    	
	    	if(ans<0) System.out.print("0 ");
	    	else System.out.print("1 ");
	    }
	    
	}

 

풀이 방법

문제만 보았을 때, 반복문 돌려서 탐색하면 되겠는데? 라는 생각을 할 법한 문제이다. 하지만 문제에서 제시된 숫자 카드의 개수 범위가 매우 크기 때문에 반복문을 돌리는 방식으로는 "틀렸습니다" 가 뜰 것이다. 따라서 이 문제는 "이분탐색"을 써야 한다. 이분탐색은 정렬되어있는 배열에서 이용 가능하기 때문에 입력받은 배열을 우선 정렬해주고, 찾고자 하는 카드를 이분탐색으로 찾아주면 된다.

 

어려웠던 점, 개선점

이분탐색을 직접 구현하려고 했을 때 테스트케이스에서 통과되지 않는 부분이 있었다. 그래서 API를 이용해 풀었는데, 아직 이 부분이 해결되지 않았다. 어떤 부분에서 문제가 있었는지 해결해볼 필요가 있을 것 같다.

/* 직접 구현해본 이분탐색 코드이다.
	static int  BS(int key,int mini,int max,int[] card) {
		if(mini<=max) {
			int mid=(mini+max)/2; 
			if(key==card[mid])
			{
				return 1;
			}
			else if(key<card[mini])
			{
				return BS(key,mini,mid-1,card);
			}
			else 
			{
				return BS(key,mid+1,max,card);
			}
		}
		return 0;
	}
	*/