[Baekjoon/JAVA] 백준 10815번 숫자 카드

문제

입/출력

 
주어지는 숫자의 범위가 매우 크기 때문에, 일일이 비교하는 방법보다는 이분 탐색 알고리즘을 이용해야 합니다.
 
 

import java.util.*;
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int cards[] = new int[n];
		
		st = new StringTokenizer(br.readLine()," ");
		
		for(int i=0; i<n; i++) {
			cards[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(cards);
		
		int m = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine()," ");
		
		for(int i=0; i<m; i++) {
			int num = Integer.parseInt(st.nextToken());
			sb.append(Search(cards, n, num) + " ");
		}
		System.out.println(sb);
		
		br.close();
		
	}
	
	public static int Search(int cards[], int n, int num) {
		int start = 0;
		int end = n - 1;
		int mid;
		
		while(start <= end) {
			mid = (start + end) / 2;
			
			if(cards[mid] == num) {
				return 1;
			}
			if(cards[mid] < num) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		
		return 0;
	}
}

 
이분 탐색을 위해선,  반드시 배열이 정렬되어 있어야 합니다.
Arrays.sort(cards) 함수로 cards 배열을 정렬하였습니다.
 
이분 탐색 알고리즘은 아래쪽 Search 메소드에 구현했습니다.
탐색할 기준이 될 배열, 배열의 length, 찾을 숫자를 입력받습니다.
 
start = 0 (배열 시작지점)
end = n - 1 (배열 마지막지점)
mid = (start + end) / 2 (배열의 중간 지점)
이렇게 초기화 합니다. mid는 탐색과정에서 계속 바뀌기 때문에 while문 안에 넣어줍니다.
 
만약, 찾을 숫자가(num) mid보다 크다면?
(start) ... [mid] ... num ... (end)  
이런 식으로 되어있겠죠? 그러면 mid 아랫부분은 볼 필요가 없습니다.
따라서 start 부분을 , mid + 1 부분으로 올려줍니다.
 
반대로, 찾을 숫자가 mid보다 작다면?
(start) ... num ... [mid] ... (end)  
mid 위쪽은 볼 필요가 없겠죠? 따라서 end 부분을 mid - 1 부분으로 낮춰줍니다.
 
이런식으로 굳이 모든 값과 비교할 필요 없이, 경우의 수를 반씩 줄여가며 효율적인 탐색이 가능합니다.
그리고 만약 [mid]값이 num과 같다면? 찾은 것이니 1을 리턴합니다.
배열에서 끝까지 찾지 못했다면, while문 탈출 후 0을 리턴합니다.
 
이렇게 이분 탐색 알고리즘을 이용하여 문제를 해결할 수 있었습니다.