[백준 1920] 수 찾기

🫡 문제

백준 1920 - 수찾기

🫡 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int A[];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // 숫자 개수
		A = new int[N]; // X라는 정수가 존재하는지 알아내야하는 숫자들
		for (int i = 0; i < N; i++) {
			A[i] = sc.nextInt();
		}

		Arrays.sort(A); // 이진탐색을 위한 숫자 오름차순 정렬

		int X = sc.nextInt(); // 찾아야 하는 숫자 갯수

		for (int i = 0; i < X; i++) {
			int index = sc.nextInt();

			int result = bs(index);
			System.out.println(result);
		}

	}

	public static int bs(int index) {
		int start = 0;
		int end = A.length - 1;

		while (start <= end) {

			int mid = (start + end) / 2; 		// 중앙값 구하기

			if (A[mid] > index) { 				// 중앙값>찾아야하는 숫자
				end = mid - 1; 					// 끝값을 중앙값보다 작게 초기화
			} else if (A[mid] < index) { 		// 중앙값<찾아야하는 숫자
				start = mid + 1; 				// 시작값을 중앙값보다 크게 초기화
			} else if (A[mid] == index) { 		// 숫자 존재
				return 1; 						// 1 반환
			}
		}
		return 0; // 존재하지 않음

	}

}

🫡 풀이

N개의 정수(A) 안에 숫자 X(index)가 존재하는지 알아내는 프로그램입니다.
이진 탐색(binary search) 을 통해서 중앙값(이하 mid)을 지정한 후에
찾고자하는 값(이하 index)을 비교해주었습니다.

• index 가 mid보다 크면 시작값을 mid+1
• index 가 mid보다 작으면 끝값을 mid-1

시도)
존재하는지 찾아야 하는 숫자들도 배열(M)로 선언해서
bs에 하나씩 start, end, index prameter를 넣어주고 있었는데
하다보니 좀 헷갈려서(ㅠㅠ) 반복문을 돌려 숫자를 입력하는 데로 bs를 호출해주었습니다.