JAVA 백준 문제풀이 (21) 10815: 숫자 카드

 



이진 탐색 + 정렬 문제다.

정렬은 직접 구현할 필요 없고 이진 탐색은 자바 Arrays 에서 제공하는 API인 binarySearch()가 있지만 0, 1을 출력해주는 메서드는 아니기 때문에 오버라이딩하던지 새로 만들어서 구현하던지 하면 된다.

 

이진 탐색은 무엇인가? 우리(나) 같은 문돌이한테는 벌써 뭔가 전문적인 용어처럼 느껴지면서 겁이 날 수 있지만 정말 쉬운 개념이다.

우리가 책을 읽을 때 총 800페이지가 있는 책에서 700 페이지를 찾아야 한다면 책을 어떻게 펼치는가?

 

1. 책을 일단 절반으로 펼칠 것이다.

2. 그렇게 400 페이지가 나왔다고 생각해보자, 우리가 찾는 페이지는 700페이지이기 때문에 더 이상 400페이지 이전은 확인해볼 필요가 없다.

3. 그러면 앞 페이지들은 배제하고 다시 절반 정도의 위치를 펼쳐볼 것이다.

4. 그리고 적당한 페이지까지 이를 반복한 뒤 한 장씩 넘겨서 정확한 페이지를 찾게 된다.

 

여기서 절반씩 펼쳐가며 탐색하는 방식이 이진 탐색(Binary Search)이고 한 페이지씩 넘기며 찾는 방법은 선형 탐색(Linear Search)라고 한다.

인간이라면 애초에 정확하게 반씩 나눠가며 탐색하지도 못할 뿐더러 선형 탐색을 섞을 수 밖에 없겠지만 컴퓨터는 이진 탐색만 이용해서 선형 탐색보다 훨씬 효과적인 방법으로 데이터를 찾아낼 수 있다.

 

쩝.. 문제풀이인데 이론 설명이 너무 길었다.

 

결론은 배열에서 특정 값을 찾고 싶을 때 이진 탐색을 활용하여 효율적으로 찾을 수 있으며, 이 이진 탐색이라는 것은 인덱스를 반쪽으로 나눈 뒤 ( 반쪽보다 찾으려는 값이 큰가요? ) => ( 반쪽 +1 인덱스부터 마지막 인덱스까지를 다시 반쪽으로 나눈다 ) => ( 반쪽의 반쪽보다 찾으련느 값이 큰가요? ) => .. => (어? 반을 아무리 나눠도 해당 값이 없네? 0) || (값을 찾았으니 1 반환!) 둘 중 하나의 결과가 나올 떄까지 반복하면 된다는 것이다.

 

정말 쉽고 별것 아니지만 직접 구현하면 뭔가 된 것 같고 짜릿하니 왠만하면 답을 보지 말고 직접 구현해보자.

 

 

 

 

 

 

정답은 아래 ⬇️

 

 

 

 

 

 

 

 

 

나는 스트림으로 정렬, 배열 자료형 변경을 해결했으나 스트림이 익숙하지 않다면 반복문 만들어서 바꿔도 상관 없다.

손가락이 아플 뿐.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int draw = Integer.parseInt(br.readLine()); // 의미 없는 입력값. 사용되지 않음.
        int[] cards = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int userDraw = Integer.parseInt(br.readLine()); // 의미 없는 입력값. 사용되지 않음.
        int[] userCards = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        // 이진탐색은 반드시 정렬을 해줘야 적용 가능하다.
        cards = Arrays.stream(cards).sorted().toArray();

        for (int num : userCards) {
            sb.append(mySearch(cards,num)).append(" ");
        }

        System.out.println(sb);
    }


     // 이진 탐색 메서드
    public static int mySearch(int[] arr, int num) {

        // 처음에는 시작점인덱스를 0, 배열 길이로 잡는다.
        // 중간 지점은 계속 바뀌므로 0으로 시작
        int start = 0;
        int end = arr.length-1;
        int mid = 0;

        // 인덱스가 하나만 남을 때까지 탐색한다
        while ( start <= end ) {
            // mid는 늘 쪼갠 배열의 중간
            mid = (start+end)/2;
            if ( num == arr[mid] ) {
                return 1;
            } else if ( num > arr[mid] ) {
                start = mid+1;
            } else if ( num < arr[mid] ) {
                end = mid-1;
            }
        }
        return 0;
    }
}