[백준] 1920 수 찾기_ JAVA
● 문제
● 풀이
출처 : https://st-lab.tistory.com/261
[백준] 1920번 : 수 찾기 - JAVA [자바]
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음
st-lab.tistory.com
이분 탐색 개념 설명 :
'정렬 된 배열'이 들어온다는 가정하에, 파라미터로 배열을 찾으려는 값인 key 변수가 들어온다고 한다.
기본적으로 세팅할 변수는 다음과 같다.
/**
* @param arr 정렬된 배열
* @param key 찾으려는 값
* @return key와 일치하는 배열의 인덱스
*/
public static int binarySearch(int[] arr, int key){
int lo = 0; //탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스
}
이분 탐색 과정을 거치기 위해서는 탐색 범위를 알아야 하는데, 그렇기에 탐색 범위의 왼쪽 끝과 오른쪽 끝을 가리키는 변수가 필요하다. 이를 lo, hi로 두었다.
그 다음으로 할 것은 탐색 과정을 반복하기 위한 반복문 작성이다. 반복 조건은 왼쪽 끝과 오른쪽 끝이 같은 경우까지 탐색하는 것이다.
lo, hi로 탐색 범위를 가리키는 변수를 두었다. 탐색 범위가 오른쪽 끝과 왼쪽 끝이 같을 때까지 탐색한다고 하면,
이는 lo가 hi보다 커질 때이다. 즉, lo > hi 이라면 더이상 반복하지 않는 것이다.
아래와 같이 반복문 작성
public static int binarySearch(int[] arr, int key){
int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length -1; // 탐색 범위의 오른쪽 끝 인덱스
// lo가 hi보다 커지기 전까지 반복
while (lo <= hi){
}
}
이제 반복분 내에 탐색과정을 본격적으로 구현한다.
이분 탐색에서 크게 보면 세 가지 과정을 거쳤다.
1. 중간 인덱스를 구한다.
2. 중간값과 key 값을 비교한다.
3. 비교값에 따라 범위를 왼쪽, 오른쪽 혹은 값이 같은 경우는 해당 인덱스를 반환한다.
public static int binarySearch(int[] arr, int key) {
int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스
// lo가 hi보다 커지기 전까지 반복
while (lo <= hi) {
//중간 위치
int mid = (lo + hi) / 2;
//key 값이 중간 위치의 값보다 작을 경우
if(key < arr[mid]){
}
//key 값이 중간 위치의 값보다 클 경우
else if(key > arr[mid]){
}
//key 값이 중간 위치의 값과 같을 경우
else {
}
}
}
위처럼 세가지 경우의 수가 나뉘고, 해당 경우에 따라 위치를 재조정해야 한다.
먼저, key < arr[mid] 인 경우에는?
key값이 배열의 중간보다 왼쪽에 있다는 의미일 것이다. 즉. 탐색 범위의 오른쪽 끝을 가리키는 hi가 재조정되어야 한다는 의미이다.
어떤 값으로 재조정 되는지를 생각해보면 우리가 찾는 key값은 lo~mid 사이에 있다는 것이다.
이 때, arr[mid]는 이미 비교작업을 했으니 mid(중간)을 제외한 왼쪽 부분을 탐색 범위로 보면 된다.
(예를 들어 up&down 게임에서 1~100 범위에서 50을 외쳤는데 down 이면 그 다음은 50을 제외한 1~49사이의 수가 탐색 범위인 것과 같은 의미다)
즉, hi = mid - 1;이 제조정 된 값이 되는 것이다.
그 다음으로 key > arr[mid] 인 경우에는
위와 반대로 key값이 배열의 중간보다 오른쪽에 위치한다는 의미이다.
즉, 탐색 범위의 오른쪽 끝을 가리키는 lo가 재조정되야 한다.
즉, 재조정 되는 lo의 값은 lo = mid + 1 이 되는 것이다.
마지막으로 else 조건 key == arr[mid] 인 경우는 이미 찾고자하는 값을 찾았으므로 mid를 반환하면 된다.
찾고자 하는 값이 존재하지 않을 경우에는 return -1;
public static int binarySearch(int[] arr, int key) {
int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스
// lo가 hi보다 커지기 전까지 반복
while (lo <= hi) {
//중간 위치
int mid = (lo + hi) / 2;
//key 값이 중간 위치의 값보다 작을 경우
if (key < arr[mid]) {
hi = mid - 1;
}
//key 값이 중간 위치의 값보다 클 경우
else if (key > arr[mid]) {
lo = mid + 1;
}
//key 값이 중간 위치의 값과 같을 경우
else {
return mid;
}
}
//찾고자 하는 값이 존재하지 않을 경우
return -1;
}
위의 방식을 토대로 작성한 최종 코드.
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
StringBuilder sb = new StringBuilder();
int M = in.nextInt();
for (int i = 0; i < M; i++) {
if(binarySearch(arr, in.nextInt()) >=0){
sb.append('1').append('\n');
}
else{
sb.append('0').append('\n');
}
}
System.out.println(sb);
}
public static int binarySearch(int[] arr, int key) {
int lo = 0; // 탐색 범위의 왼쪽 끝 인덱스
int hi = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스
// lo가 hi보다 커지기 전까지 반복
while (lo <= hi) {
//중간 위치
int mid = (lo + hi) / 2;
//key 값이 중간 위치의 값보다 작을 경우
if (key < arr[mid]) {
hi = mid - 1;
}
//key 값이 중간 위치의 값보다 클 경우
else if (key > arr[mid]) {
lo = mid + 1;
}
//key 값이 중간 위치의 값과 같을 경우
else {
return mid;
}
}
//찾고자하는 값이 없을 경우
return -1;
}
}