백준 10815번 : 숫자 카드

 문제

www.acmicpc.net/problem/10815

10815번: 숫자 카드

10815 숫자 카드

 

 구현 방법

단순하게 이중포문으로 풀 수도 있지만 주어진 시간 제한은 2초, N과 M은 500,000이하

시간복잡도를 계산해보면 대충 O(NM) = 25억 정도로 시간 초과를 하기 때문에 저는 이분탐색으로 풀어주었습니다.

 

 이분 탐색이란 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식으로 시간 복잡도가 훨씬 줄어들 수 있습니다.

간단하게 개념을 설명해보자면 수열이 있고 그 수열 내에서 10이라는 숫자를 찾고 싶을 때 이중 포문을 돌리면 1, 3, 5, 7을 차근차근 찾아 6번의 탐색을 거쳐야 10을 찾을 수 있습니다.

하지만 이분 탐색을 사용하게 된다면

1. 중간 값 찾기 = (시작 인덱스+마지막 인덱스)/2

2. 중간 값과 찾으려는 값 비교 -> 두 부분을 분할

2-1. 찾으려는 값이 중간 값보다 크다면 시작 인덱스 : 중간 값+1

2-2. 찾으려는 값이 중간 값보다 작다면 마지막 인덱스 : 중간 값-1

3. 찾을 때 까지 반복

을 하여 3번의 탐색을 거치면 10이라는 수를 찾을 수 있습니다.

이분 탐색의 필수 조건은 정렬입니다. 정렬을 한 후에 해야합니다.

 

 

 원래 이 문제는 이분 탐색의 정석인 문제이지만 또 다른 방법으로도 풀 수 있었습니다.

바로 Bitset 클래스를 이용하는 방법입니다. BitSet에 대한 내용은 

imgoood.tistory.com/24?category=983825

 

BitSet

간단히 정리를 해놨으니 참고하셔도 좋을거 같습니다.

 

BitSet을 이용하여 상근이가 가지고 있는 숫자 카드의 값들을 true로 만들어 놓고 M개의 정수를 받아 해당 값이 true이면 1, false이면 0을 출력해주면 됩니다. 훨씬 간단하죠?

 

 구현 코드

- 이분 탐색

package BOJ.Silver.binarySearch;

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

public class B10815_숫자카드 {
	static int N, M;
	static int[] haveC, searchC;
	static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		haveC = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i=0;i<N;i++) {
			haveC[i] = Integer.parseInt(st.nextToken());
		}
		M = Integer.parseInt(br.readLine());
		searchC = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i=0;i<M;i++) {
			searchC[i] = Integer.parseInt(st.nextToken());
		}
		// 입력 완료
		Arrays.sort(haveC); // 정렬
		
		for (int i=0;i<M;i++) {
			search(searchC[i]);
		}
		
		System.out.println(sb);
	}
	
	static void search(int search) {
		int start = 0;
		int end = N-1;
		while(start<=end) {
			int mid = (start+end)/2;
			if (haveC[mid]==search) {
				sb.append(1+" ");
				return;
			}
			if (haveC[mid]>search) end = mid-1;
			else start = mid+1;
		}
		sb.append(0+" ");
	}
}

- BitSet

package BOJ.Silver.binarySearch;

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

public class B10815_숫자카드 {
	static int N, M;
	static int[] haveC, searchC;
	static StringBuilder sb;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		BitSet bitSet = new BitSet();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
        	// 정수 범위가 -10,000,000 ~ 10,000,000까지, 음수값은 계산할 수 없으므로 음수값의 범위를 더해줌
			bitSet.set(Integer.parseInt(st.nextToken()) + 10000000); 
		}
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
        	int ans = bitSet.get(Integer.parseInt(st.nextToken()) + 10000000)?1:0;
        	sb.append(ans+" ");
        }
        System.out.println(sb);
	}
}

 

정답!