백준 S4 1920 : 수 찾기 🅾️

[문제]

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.

다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.

다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다.

모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

 

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

1920번: 수 찾기

 

[풀이]

import java.util.*;

public class Main {
	static int[] arr;
	static boolean chk;
	
	public static void binarySearch(int num, int min, int max) {
		if(max<min) return;
		
		int idx=min+(max-min)/2;
		
		if(arr[idx]==num) {
			chk=true;
			return;
		}
		
		if(arr[idx]>num) {
			binarySearch(num, min, idx-1);
		} else {
			binarySearch(num, idx+1, max);
		}
	}

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		int n=sc.nextInt();
		arr=new int[n];
		for(int i=0;i<n;i++) arr[i]=sc.nextInt();
		Arrays.sort(arr);
		
		int m=sc.nextInt();
		for(int i=0;i<m;i++) {
			int num=sc.nextInt();
			chk=false;
			binarySearch(num, 0, n-1);
			if(chk) System.out.println(1);
			else System.out.println(0);
		}
	}

}

 

어제 실패했던 문제..

오늘은 이진 탐색 공부를 하고 다시 풀었다.

 

(아래는 이진 탐색 공부한 내용 포스팅한 글!!)

알고리즘 : BinarySearch 이진 탐색

 

이진 탐색을 하며 num이 arr에 존재하면 chk를 true로 설정해주었다.

그리고 만약 chk가 true라면 1을 출력, 아니라면 0을 출력!

for문을 돌며 chk는 계속 false로 초기화해주었다.

 

 

어쨌든 코테 풀기 성공~!

실패했던 문제를 푸니까 더 성취감이 큰 것 같다 ^____^~~ 얏호