[Java] BOJ 1920 - 수 찾기

Jae Chan·2023년 3월 5일

Coding-Test

목록 보기

9/10

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력 📨

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력 📩

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력

예제 출력

알고리즘 분류

자료 구조
정렬
이분 탐색

이분 탐색(Binary Search)

이번 문제는 배열에 접근하여 원하는 값을 탐색해야하며 문제의 핵심은 이분 탐색이다.

이분 탐색은 Up & Down 게임을 떠올리면 된다. 1 - 100 의 숫자중 하나의 값을 찾는 게임이다.

👨‍💻 : 음.. 50?

👩‍💻 : 그거보다 낮은 숫자에요.

👨‍💻 : 26?

👩‍💻 : 26보다 낮아요.

👨‍💻 : 🤔 .. 13?

이런 식으로 원하는 값에 도달하기 위해 임의의 값(또는 중간 값) 보다 크고 작음을 분류하여 값을 구하는 방식이라고 생각하면 된다.

구조 및 흐름

아분 탐색의 흐름은 다음과 같다.

흐름
➡️ 인덱스 내에서 중간값을 구한다.
➡️ 중간값과 찾고자 하는 값을 비교한다.
➡️ 찾는 값이 중간 값보다 작다면 왼쪽 부분을 탐색한다.
➡️ 찾는 값이 중간 값보다 크다면 오른쪽 부분을 탐색한다.
➡️ 위 과정을 반복한다.

✅ 찾는 값이 중간 값과 같다면 값 발견!
❌ 왼쪽 값이 오른쪽 값과 같거나 크다면 값 발견하지 못한 것!

조건
✅ 배열 내 인덱스 값이 정렬 되어 있어야한다.
✅ 탐색 범위 지정을 위해 왼쪽을 가르키는 변수, 오른쪽을 가르키는 변수가 요구된다.
예시

찾으려 하는 값은 22 , 현재 배열 내 중간 인덱스의 값은 9.
➡️ 22는 9보다 크므로 중간 값 기준 오른쪽에서 탐색, 왼쪽 값을 중간 인덱스 + 1 하여 11을 왼쪽 값으로 지정.
현재 배열 내 간 인덱스의 값은 23.
➡️ 23은 22보다 작으므로 오른쪽 값을 중간 인덱스 - 1 하여 22를 오른쪽 값으로 지정.
탐색 범위가 왼쪽 값과 오른쪽 값이 같아질 때까지 위의 과정을 반복한다.

코드를 통해 구현해보면 다음과 같다.

public static int binarySearch(int[] searchArr, int key) {
	int lowIndex  = 0; // 배열 탐색 범위의 왼쪽 끝 인덱스 값
	int highIndex = searchArr.length - 1; // 배열 탐색 범위의 오른쪽 끝 인덱스 값
    
     // low 값이 high 값보다 커지기 전까지 Loop
        while(lowIndex <= highIndex)
        {
            // 찾고자 하는 배열의 중간 값
            int midIndex = (lowIndex + highIndex) / 2;

            /* key 값이 중간값 보다 작을 경우 high 값 재조정 */
            if(key < searchArr[midIndex]) {
                highIndex = midIndex - 1;
            } 
            
            /* key 값이 중간값 보다 클 경우 low 값 재조정 */
            else if(key > searchArr[midIndex]) {
                lowIndex = midIndex + 1;
            } 
            
            // key 값이 중간값과 같을 경우 값 그대로 반환
            else {
                return midIndex;
            }
        }

        // 찾는 값이 존재하지 않을 경우 -1 리턴.
        return -1; 
    }
}

여기서 핵심은 총 세가지이다.

❗key 값이 배열의 중간 값보다 작을 경우에는 지정한 오른쪽 값을 중간 값의 -1 한 값으로 지정해준다.

if(key < searchArr[midIndex]) {
                highIndex = midIndex - 1;
            }

❗key 값이 배열의 중간 값보다 클 경우에는 지정한 왼쪽 값을 중간 값의 +1 한 값으로 지정해준다.

else if(key > searchArr[midIndex]) {
                lowIndex = midIndex + 1;
            }

❗key 값이 중간 값과 같은 경우 return 값을 midIndex로 해준다.
즉, 중간 값이 키 값과 같다는 것은 값을 찾았다는 뜻.

✅ 1-2번 과정을 반복하며 lowIndex 값이 highIndex 보다 같거나 커져서 반복문을 나오게 되면 찾고자 하는 값이 없기 때문에 -1을 리턴해준다.

문제 해결 ✔️

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    // 이분 탐색 구현 메소드
    public static int binarySearch(int[] searchArr, int key) {
        int lowIndex  = 0; // 배열 탐색 범위의 왼쪽 끝 인덱스 값
        int highIndex = searchArr.length - 1; // 배열 탐색 범위의 오른쪽 끝 인덱스 값

        // low 값이 high 값보다 커지기 전까지 Loop
        while(lowIndex <= highIndex)
        {
            // 찾고자 하는 배열의 중간 값
            int midIndex = (lowIndex + highIndex) / 2;

            /* key 값이 중간값 보다 작을 경우 high 값 재조정 */
            if(key < searchArr[midIndex]) {
                highIndex = midIndex - 1;
            } 
            
            /* key 값이 중간값 보다 클 경우 low 값 재조정 */
            else if(key > searchArr[midIndex]) {
                lowIndex = midIndex + 1;
            } 
            
            // key 값이 중간값과 같을 경우 값 그대로 반환
            else {
                return midIndex;
            }
        }

        // 찾는 값이 존재하지 않을 경우 부정(-1)
        return -1; 
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int index = sc.nextInt();
        int[] arr = new int[index];

        for(int i = 0; i < index; i++) {
            arr[i] = sc.nextInt();
        }

        Arrays.sort(arr); // 배열 정렬

        StringBuilder sb = new StringBuilder();
        int findIndexValue = sc.nextInt();

        for(int i = 0; i < findIndexValue; i++) {
            if(binarySearch(arr, sc.nextInt()) >= 0) {
                sb.append(1).append("\n");
            } else {
                sb.append(0).append("\n");
            }
        }
        System.out.println(sb);
        sc.close();
    }
}