[백준]1920번 수 찾기(JAVA)

0. 문제 링크

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

1920번: 수 찾기

 

1. 문제 설명

1) M개의 정수 배열의 수가 N개의 정수 배열 A에 존재하는지 출력

 

2. 입출력

// input
5 // N
4 1 5 2 3 // A[1], A[2], ... , A[N]
5 // M
1 3 7 9 5

 

3. 코드

import java.util.*;

public class b1920 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		
		int N = sc.nextInt(); // N개의 정수
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr); // 정렬
		
		int M = sc.nextInt(); // M개의 정수
		for (int i = 0; i < M; i++) {
			if(binarySearch(arr, sc.nextInt()) >= 0){ // arr에 존재하는지
				sb.append(1).append("\n"); // 존재하면 1 추가
			} else {
				sb.append(0).append("\n"); // 존재하지 않으면 0 추가
			}
		}
		
		System.out.println(sb);
	}

	private static int binarySearch(int[] arr, int key) {
		int start = 0; // 시작 위치
		int end = arr.length - 1; // 종료 위치
		
		while(start <= end) { // 시작 위치보다 종료 위치가 작거나 같을 때까지 반복
			int mid = (start + end) / 2; // 중간 지점
			
			if(key < arr[mid]){ // key 값이 중간 지점보다 작으면
				end = mid - 1; // 종료 위치 조정
			} else if(key > arr[mid]) { // key 값이 중간 지점보다 크면
				start = mid + 1; // 시작 위치 조정
			} else { // key 값과 중간 지점 값과 같으면
				return mid; // mid가 찾는 값임
			}
		}
		
		return -1;
	}
}

 

실행 결과

 

4. 회고

1) N개의 정수 배열이 최대 100,000개까지 주어질 수 있기 때문에 일일히 비교하는 것은 시간 초과

2) binarySearch로 이진 탐색을 통해서 반씩 나누어서 살펴보면서 찾으려는 숫자가 존재하는지 파악

 

5. Github