BOJ - 1920 수 찾기

leehyunjon·2022년 5월 26일

boj 이분 탐색

Algorithm

목록 보기

46/162

1920 수 찾기 : https://www.acmicpc.net/problem/1920

Problem

Solve

N이 100000이므로 이중 반복은 불가능하다. M의 수를 반복하는데 O(100000), N의 수에 taget여부를 확인하는데 binary_search O(logN)으로 해결할수 있다.

binary_search는 정렬된 배열에서 target(하나의 값)을 찾는 알고리즘이다.

찾고자하는 target을 설정하고 배열을 오름차순 정렬한다.
두개의 포인터 start, end를 통해 이분 탐색을 하게된다.
- while(start<=end) 동안 이분 탐색을 실행한다.
arr[mid]>target 이라면 end = mid-1
- target을 찾기 위해 범위를 mid의 왼쪽으로 좁힌다.
arr[mid]<target 이라면 start = mid+1
- target을 찾기 위해 범위를 mid의 오른쪽으로 좁힌다.
arr[mid] == target 이라면 1을 반환한다.
모든 배열을 탐색했을때 target이 존재하지 않는다면 0을 반환한다.

Code

public class 수찾기 {
	static int[] arr;
	static int[] arr2;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
        //기준 배열
		arr = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int M = Integer.parseInt(br.readLine());
        //비교할 배열
		arr2 = new int[M];
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<M;i++){
			arr2[i] = Integer.parseInt(st.nextToken());
		}

		//이분탐색할 배열을 정렬한다.
		Arrays.sort(arr);

		StringBuilder sb = new StringBuilder();
		for(int num : arr2){
			int result = binarySearch(num);
			sb.append(result);
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static int binarySearch(int num){
		int start=0;
		int end=N-1;

		//이분탐색은 start와 end가 겹쳐도 비교하고 끝낸다.(하나의 값을 찾기 위해)
		while(start<=end){
			int mid = (start+end)/2;

			//arr[mid]가 target보다 크다면 mid왼쪽부분으로 범위를 좁힌다.
			if(num<arr[mid]){
				end = mid-1;
			}else if(num>arr[mid]){
            //arr[mid]가 target보다 작다면 mid 오른쪽부분으로 범위를 좁힌다.
				start = mid+1;
			}else{
            //arr[mid] == target이라면 1 반환
				return 1;
			}
		}
        //arr배열에 target이 존재하지 않다면 0 반환
		return 0;
	}
}