(JAVA) 백준 문제 풀이 - 이분 탐색 단계 - 1920번 수 찾기 (실버 4)

이번 문제는 이분 탐색을 이용하여 주어진 수가 특정 배열에 존재하는지 판단하는 프로그램을 작성하는 문제이다.

이분 탐색의 첫 문제인 만큼 이분 탐색이 무엇이고 어떻게 만들어야 하는지 정리해본다.

---

이분 탐색이란?

어렸을 때 한번쯤 Up&Down 게임을 해본적이 있을 것이다.

상대방이 숫자를 생각해 내면 내가 숫자를 추측해서 말하고 상대방이 그 수가 정답보다 큰지 작은지 말해주는 게임이다.

이분 탐색 알고리즘은 위의 게임과 거의 유사하다.

특정 값을 찾을 때, 중간 값을 기준으로 값을 비교하고 적으면 처음 부터 중간까지, 크다면 중간부터 끝까지 탐색하는 것이다.

다만, 이렇게 하기 위해서 기준 배열이 정렬이 되어있어야 한다는 것이 주의점이다.

예를 들어서, 1,5,3,2,4라는 값이 있고 2라는 값을 찾는다고 생각해보자.

1

5

3

2

4

여기서 중간 값은 3이 될 것이고 던진 2와 3이 일치하지 않으니 1~3까지에서 다시 2를 탐색하게 될 것이다.

하지만, 앞서 말한대로 정렬이 되어있지 않으면 1,5,3에서 찾게 될테니 결국 제대로 답이 나오지 않는 것이다.

반대로 위의 배열을 정렬하여 찾는다고 생각해보자.

1

2

3

4

5

중간 값은 3이니 아래쪽 인덱스에서 다시 한번 찾게 될 것이다.

1

2

3

이렇게 되면 중간 값은 2가 되고 정상적으로 값을 찾을 수 있게 되는 것이다.

반대로 4를 찾는 경우는 중간값 보다 높으므로 3~5에서 찾게 될 것이다.

이런식으로 이분 하여 탐색한다 하여 이분 탐색이라고 부르는 것.

 

정리하자면 이분 탐색에서 중요한 것은 다음과 같다.

1. 기준 배열을 오름차순으로 정렬한다.
2. 중간 값을 계산한다.
3. 탐색할 값과 중간 값이 맞지 않으면 중간 값과 탐색할 값을 비교한다.
4. 값이 큰 경우 중간값+1(중간값은 이미 같지 않으므로 +1 해준다) ~ 마지막 인덱스까지 다시 탐색한다.
5. 값이 작은 경우 0부터 중간값-1(중간값은 같지 않으므로 -1한다)까지 다시 탐색한다.
6. 값이 없는 경우의 로직을 만든다.

그렇다면 위의 로직을 구현하기 위해서 2가지 방법이 있는데 재귀를 통해서 만들던지 반복문을 통하여 만들면 된다.

자세한 내용은 다음 블로그에 정리가 잘 되어있으니 한번 살펴보는 것을 추천한다.

https://minhamina.tistory.com/127

이진탐색 = 이분탐색 (Binary Search) - Java로 구현

---

이분 탐색을 만들자!

그럼 본격적으로 로직을 만들어 보자.

문제를 살펴보면 첫번째 줄에 기준 배열의 갯수 k가 주어지고, 2번째 줄에 기준 배열이 들어온다.

그 후, 찾을 갯수 n개와 4번째 줄에 찾아야 할 숫자 배열이 들어오게 된다.

로직을 짜는건 그다지 어렵지 않았는데, 코드를 보면서 같이 살펴보자.

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

class Main{
    public static int n,m;
    public static int[] arr;
    public static String[] str;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        str = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(arr);

        m = Integer.parseInt(br.readLine());
        str = br.readLine().split(" ");

        for (String s : str) {
            System.out.println(findn(Integer.parseInt(s),0,n-1));
        }

    }

    public static int findn(int a,int st, int end) {
        if (st > end) {
            return 0;
        }
        int mid = (st + end) / 2;

        if (arr[mid] == a) {
            return 1;
        } else if (arr[mid] > a) {
            return findn(a, st, mid - 1);
        } else {
            return findn(a, mid + 1, end);
        }
    }
}

나는 재귀를 이용하여 로직을 구성하였는데 (실제 성능적인 측면은 반복문을 활용하는 것이 더 좋다고 한다)

우선 입력값을 각각 담아두고, 값을 구해야하는 배열이 들어올때, 각각을 findn 메서드로 던져준다.

초기값은 0부터 입력된 갯수 n-1(인덱스로 계산되므로 -1을 해주어야한다.) 즉, 처음부터 끝까지이다.

메서드 안에서는 탈출 조건이 우선 나오게 되는데 if 문을 통하여 시작 값이 끝 값보다 크다면 0을 리턴하도록 하였다.

만약 그게 아니라면 시작값 + 끝값 / 2를 하여 중간 값을 구하고, 기준 배열의 중간값 인덱스와 던져진 a를 비교한다.

두개가 같지 않다면 중간값을 기준으로 크고 작음을 비교하여 작은 경우 0 ~ 중간값 -1 까지, 크다면 중간값 + 1 ~ 종료값 까지 재귀하도록 하였다.

---

정리를 마치며...

결과적으로 크게 어려운 문제는 아니였다. 이분 탐색의 기초를 잡는 느낌이라 할까... 앞으로 어떤 식으로 이 알고리즘이 적용되는지를 계속 살펴봐야 할 것이다.

---

참고자료

https://minhamina.tistory.com/127