[이분 탐색] 백준 10815 - 숫자 카드 (자바)

이분 탐색 기초

 

내가 보려고 씀

 

문제 : https://www.acmicpc.net/problem/10815

 

 

이분 탐색 문제지만 

사실상 이분 탐색 처음? 공부하는 거라 걍 내 방식대로 풀어봄.

ArrayList에 담아서 contains로 판단.

 

결과는 당연히 시간 초과.

 

 

[기존 코드 (ArrayList - 시간 초과)]

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

public class Main {
	
	static int N, M;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		List<String> numList = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			numList.add(st.nextToken());
		}
		
		M = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			if(numList.contains(st.nextToken())) sb.append(1 + " ");
			else sb.append(0 + " ");
		}
		
		System.out.println(sb);

	}

}

 

 

---

 

이분 탐색

이분탐색할 배열은 반드시 정렬이 되어야 한다.

어떠한 요소 N을 찾으려고 할 때 모든 배열을 보지 않고,
배열의 중간값이 N보다 큰 지 작은 지 검사합니다.
만약 중간값이 N보다 작으면 중간값 이하는 모두 볼 필요가 없습니다.
반대로, N보다 중간값이 크면 중간값 이상은 볼 필요가 없어집니다.
이와 같은 방식으로 배열의 중간값과 N을 계속해서 비교해 나가는 것이 핵심입니다.

출처 : https://steady-coding.tistory.com/40

 

 

 

[수정 코드 (이분 탐색)]

출처 : https://hoho325.tistory.com/140

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

public class Main {
	
	static int N, M;
	static int[] num;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		num = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(num);
		
		M = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < M; i++) {
			int result = binarySearch(Integer.parseInt(st.nextToken()));
			
			if(result != -1) sb.append(1 + " ");
			else sb.append(0 + " ");
		}
		
		System.out.println(sb);

	}
	
	public static int binarySearch(int target) {
		int left = 0;
		int right = num.length - 1;
		int mid;
		
		while(left <= right) {
			mid = (left + right) / 2;
			if(num[mid] < target) left = mid + 1;
			else if(num[mid] > target) right = mid - 1;
			else return mid;
		}
		
		return -1;
	}

}