Baekjoon_1920_수찾기

문제 설명

1920번: 수 찾기

 

• N개의 정수(모든 수는 integer범위에 들어옴)
• M개의 수 각각이 N개의 정수중에 있는지 없는지 판단

=> 있으면 1, 없으면 0 출력

 

 

문제 풀이

이 문제는 이분탐색(Binary Search)방식으로 푸는 문제이다.

 

이분탐색은 양 끝(left, right)을 기준으로 중간(mid) 값이 목표값(num)보다 클 경우 left부터 mid-1범위를 탐색,
작을경우 mid+1부터 right범위를 탐색하며 점점 범위를 좁혀나가고, 최종적으로 right값이 left보다 작아졌을 때 해당 수를 찾는 방식이다.

 

하지만 이번에는 배열에 담아 해당 수를 판단해야 하는 문제였다.

 

따라서 배열에 입력을 받고, 정렬을 한 후 이분 탐색을 수행하는데, 배열의 중간에 위치한 값과의 비교를 통해 이분 탐색을 진행했다.

 

또한 right값이 left보다 작아졌을 경우는 배열 내에서 같은 값을 찾지 못했음을 의미하여 false를 반환하도록 구현했다.

 

문제 풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
 * 이분탐색 문제
 */

public class _1920_수찾기 {
	static int N;
	static int numArray[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		StringTokenizer st = new StringTokenizer(in.readLine());
		numArray = new int[N];
		for (int i = 0; i < N; ++i) {
			numArray[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(numArray);	//배열 정렬
		
		int M = Integer.parseInt(in.readLine());
		st = new StringTokenizer(in.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < M; ++i) {
			int num = Integer.parseInt(st.nextToken());
			sb.append((BinarySearch(0,N-1,num)?"1":"0") + "\n");
		}
		System.out.println(sb.toString());
	}
	
	//이분탐색
	static boolean BinarySearch(int startIdx, int endIdx, int num) {
		if(startIdx > endIdx) {	//배열 안에서 같은 수를 못찾았을 때
			return false;
		}
		
		int mid = (startIdx + endIdx) /2;
		boolean result = false;
		if(numArray[mid] < num) {	//중간값이 num보다 크면
			result = BinarySearch(mid+1,endIdx,num);
		}else if(numArray[mid] > num) {	//중간값이 num보다 작으면
			result = BinarySearch(startIdx,mid-1,num);
		}else {	//num과 중간 값이 같으면
			result = true;
		}
		
		return result;
		
	}
}