[백준] 1920 : 수 찾기 - JAVA

🙋이진탐색 이용!

문제분석

N의 최대범위가 100,000이므로 단순 반복문으로는 이 문제를 풀 수 없다.
100,000 * 100,000이므로 O(10^10)이라서 시간제한 2초를 초과하기 때문이다.

따라서 이진탐색을 적용해 O(nlogn)의 시간복잡도로 풀 수 있다.
-> 이진탐색은 정렬을 가정하므로 정렬함수도 사용한다.
라이브러리에서 사용되는 정렬의 시간복잡도는 O(nlogn)이므로, O(nlogn + logn)인데 이는 O(nlogn)이 된다.

---

Troubleshooting

public class findNumber29 {
public static int[] A;
public static int[] find;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		A = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		int M = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			find[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=0; i<M; i++) {
			bw.write(binarySearch(0,N-1, find[i]) + "\n");
		}
		bw.flush();
		bw.close();
	}
	public static int binarySearch(int start, int end, int target) {
		while (start <= end) {
			int mid = (start + end) /2;
			if(A[mid] == target) return 1;
			else if(A[mid] < target) start = mid+1;
			else end = mid-1;
		}
		return 0;
	}
}

문제

java.lang.NullPointerException이 났다.

원인

find배열을 초기화하지 않았다.

해결

M을 입력받은 후, find = new int[M];를 추가했다.

Troubleshooting 2

문제

예제1에 대한 결과가 이상하다.
게다가 예제 1 입력 복붙했는데, '1 3 7 9 5'다음줄에 0을 또 입력받은건 뭐지?

복붙하지않고, 직접 입력해보니 5번째줄에 0을 또 입력받진 않는다..

원인

이진 탐색은 정렬된 배열에서 수행해야한다는 중요한 포인트를 놓쳤다!!

해결

이진탐색 전 Arrays.sort(A)로 오름차순정렬하는 코드를 추가했다.

---

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.Arrays;

public class Main {
public static int[] A;
public static int[] find;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		A = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(A);
		int M = Integer.parseInt(br.readLine());
		find = new int[M];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			find[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<M; i++) {
			bw.write(binarySearch(0,N-1, find[i]) + "\n");
		}
		bw.flush();
		bw.close();
	}
	public static int binarySearch(int start, int end, int target) {
		while (start <= end) {
			int mid = (start + end) /2;
			if(A[mid] == target) return 1;
			else if(A[mid] < target) start = mid+1;
			else end = mid-1;
		}	
		return 0;
	}
}

---

헷갈린 부분

이진탐색을 언제까지 반복해야하는지 헷갈렸다.
while(start <= end)로 start와 end의 순서가 꼬이기전까지 반복하는데(값이 없을경우) 이에대해 명확히 증명하기위해 상황을 살펴봤다.

---

코드 개선

for(int i=0; i<M; i++) {
	find[i] = Integer.parseInt(st.nextToken());
}
for(int i=0; i<M; i++) {
	bw.write(binarySearch(0,N-1, find[i]) + "\n");
}

이렇게 두 개의 for문으로 나뉘어져있는 코드를 합쳤다. 아래와 같이.

for(int i=0; i<M; i++) {
	find[i] = Integer.parseInt(st.nextToken());
	bw.write(binarySearch(0,N-1, find[i]) + "\n");
}

주의할 점 및 공부한 사항

• 이진탐색을 사용하려면, 정렬을 먼저 해야한다!!!
• 자바 정렬
  Arrays.sort(정렬할 배열명) = 오름차순 정렬
  Arrays.sort(정렬할 배열명, Collections.reverseOrder()); = 내림차순 정렬