[Java] 백준 1920번 문제 (수 찾기)

문제설명

 

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main
{
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		int N = Integer.parseInt(br.readLine());
		int arr[] = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		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());
		for(int i = 0; i < M; ++i)
		{
			int tmp = Integer.parseInt(st.nextToken());
            //(Arrays.binarySearch() 설명
            //배열에서 찾고자하는 정수가 있다면 해당 인덱스를 리턴
            //정수가 없다면 음수를 리턴
			if(Arrays.binarySearch(arr, tmp) >= 0) sb.append(1).append("\n"); 
			else sb.append(0).append("\n");
		}
		System.out.println(sb);
	}
}

 

설명

• 수의 범위가 매우 크기 때문에 선형 탐색을 하면 무조건 시간 초과가 날 것으로 판단했다.
• 그래서 이진 탐색으로 구현했다.
• Arrays.binarySearch API를 이용하여 간단하게 구현했다.

2023.01.27 - [자료구조 & 알고리즘/알고리즘] - [JAVA] 이진 검색(Binary Search)

[JAVA] 이진 검색(Binary Search)