[백준] 1920번 : 수 찾기 - 자바(JAVA) 풀이

백준 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을 출력한다.

예제1

입력
5
4 1 5 2 3
5
1 3 7 9 5

출력
1
1
0
0
1

해설

이진탐색을 이용하여 풀었습니다.

접근방식

1. 주어진 n개의 정수를 arr에 담아서 정렬(sort)합니다.

2. 정렬된 배열을 반씩 나누어 탐색한 후 middle값이 key와 같아지면 return합니다.

답안

제가 직접 푼 코드입니다. 재귀호출을 이용하였습니다.

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	static int n, m, key, result;
	static int[] arr;
	
	private static void binarySearch(int left, int right) {
		int middle = (left + right) / 2;
		if(arr[middle] == key) {
			result = 1;
			return;
		}
		else if(left >= right) return;
		else if(arr[middle] > key) binarySearch(left, middle - 1);
		else binarySearch(middle + 1, right);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < m; i++) {
			key = Integer.parseInt(st.nextToken());
			result = 0;
			binarySearch(0, n - 1);
			System.out.println(result);
		}
	}
	
}

다른 분들의 코드를 참고하여 가독성과 시간을 보완하였습니다.

import java.io.*;
import java.util.StringTokenizer;
import java.util.Arrays;

public class Main {
	static int[] arr;
	
	private static int binarySearch(int key) {
        int left = 0;
        int right = arr.length - 1;

        while(left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] > key) {
                right = mid - 1;
            } else if (arr[mid] < key) {
                left = mid + 1;
            } else {
                return 1;
            }
        }
        return 0;
    }
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		arr = new int[n];
		
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		int m = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < m; i++) {
			sb.append(binarySearch(Integer.parseInt(st.nextToken()))).append('\n');
		}
		System.out.println(sb);
	}
	
}

학생이라 부족한 점이 있을 수 있습니다. 조언 및 피드백은 언제든지 환영입니다!