[백준/자바] 1920번: 수 찾기

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

1920번: 수 찾기

---

이 문제를 처음 보고 든 생각난 풀이는 그냥 배열을 리스트로 변환한 후 contains를 사용하는 것이었다. 

되게 간단한 문제같은데 정답률이 30%도 안되는 걸 보고 "이렇게 푸는건 아니구나" 싶었다.

 

처음 작성한 코드는 다음과 같다.

import java.io.*;
import java.util.*;

public class Boj_1920 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		Integer [] arr = new Integer[N];
		
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		ArrayList<Integer> list = new ArrayList<>(Arrays.asList(arr));
		
		for(int i = 0; i<M; i++) {
			if(list.contains(Integer.parseInt(st.nextToken())))
				System.out.println(1);
			else
				System.out.println(0);
		};
	}
}

 

역시나 "시간초과"가 떴고, 문제를 다시 읽어보니 N, M의 범위가 100,000 까지였다.

즉, 최악의 경우엔 반복문을 10 ^ 10번 실행해야한다는 뜻이다.

따라서 빠르게 값을 찾는 방법이 필요했고, 이진탐색으로 해결하였다. 

자바에서 이진탐색을 사용하는 방법은 두 가지가 있다.

 

• 직접 구현
• Arrays.binarySearch 사용

두 방법을 모두 이용해 풀어보았다.

 

1. 직접 구현

 

이진 탐색 전에 배열 정렬해주기!

import java.io.*;
import java.util.*;

public class Boj_1920 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int [] arr = new int[N];
		
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		Arrays.sort(arr);
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());
			System.out.println(binSearch(num, arr));
		};
	}
	
	static int binSearch(int x, int[] arr) {
		int start = 0;
		int end = arr.length-1;
		while(start <= end) {
			int mid = (start + end) / 2;
			if(arr[mid] > x) {
				end = mid - 1;
			}else if(arr[mid] < x) {
				start = mid + 1;
			}else
				return 1;
		}
		return 0;
	}
}

 

2. 라이브러리 사용

import java.io.*;
import java.util.*;

public class Boj_1920 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int [] arr = new int[N];
		
		for(int i = 0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		Arrays.sort(arr);
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(st.nextToken());
			if(Arrays.binarySearch(arr, num)>=0)
				System.out.println(1);
			else
				System.out.println(0);
		};
	}
}

 

실행 결과는 다음과 같다.

아래가 직접 구현 / 위가 라이브러리 사용했을 때의 결과이다.

 

 

결론은

범위가 클 때 특정 값을 찾아야할 경우 이진탐색을 사용하자!