[백준 - 1920][Java] 수 찾기

안녕하세요, 성조입니다.

이 문제는 Java 11 버전을 기준으로 풀이됐습니다.

 

한참 Python 코드를 올리다가 갑자기 뜬금 없는 Java 문제의 출현이네요.

나름 많이 실패하고, 이유를 찾아서 찾아서 풀어냈는데 그냥 넘겨 두기에는 아쉬움이 있을 것 같아서 풀었던 내용들을 정리작성해 놓으려 합니다.

 

 

문제 출처

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

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

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
						
			int N = Integer.parseInt(br.readLine());
			int one_num[] = new int[N];
			
			StringBuilder sb = new StringBuilder();
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			for(int i=0; i<N; i++) {
				one_num[i] = Integer.parseInt(st.nextToken());
			}
			
			Arrays.sort(one_num);
			
			int M = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			
			
			for(int j=0; j<M; j++) {
				if(binarySearch(one_num, Integer.parseInt(st.nextToken())) >=0) {
					sb.append(1).append("\n");
				}
				else {
					sb.append(0).append("\n");
				}
			}
			System.out.println(sb);
			
		}catch(IOException e){
			System.out.println(e.toString());
		}
	}
	
	public static int binarySearch(int[] array, int target){

		int start = 0;
		int end= array.length-1;

		while(start<=end){
			int mid = (start+end)/2;	

			if(array[mid] == target){
	 			return 1;
			}else if(array[mid] > target){
				end= mid-1;
			}else{
	 			start= mid+1;
	 		}
	 	}
	 	return -1;
	}
}

 

풀이

1) 이진 탐색을 활용하여 문

 

 

---

오타나 이해가 안 가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

 

다음 포스팅 때 뵙겠습니다.