[백준_java] 숫자 카드 (10815번) // 이진탐색, 이분탐색

문제

상근이는 숫자카드 뭉치 N을 가지고 있다.
숫자카드 뭉치 M이 주어졌을 때,  M의 카드들이 상근이가 가진 카드라면 1을 아니라면 0으로 반환하는 문제이다.
반환은 한개씩이 아닌 한줄에 모두 출력이 되어야하며 공백문자로 구분 짓는다.

 

내 풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] cards = new int[N];
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            sb.append(binarySearch(cards, tmp) + " ");
        }
        bw.write(sb.toString() + "\n");
        bw.flush();
        br.close();
        bw.close();
    }
    public static int binarySearch(int[] cards, int search) {
        int left = 0;
        int right = cards.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (search == cards[mid]) {
                return 1;
            } else if (search < cards[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
}

 

리뷰

이진탐색을 공부하며 풀게 된 문제이다. binarySearch 메서드를 만들어서 풀어봤다.
오름차순 정렬만 돼 있는 이진탐색 문제라면 코드 자체가 큰 변화 없이 풀어낼 수 있는 것 같다.

카드뭉치N을 기준으로 left와 right(카드뭉치N.length - 1)을 찾아,
(left + right) / 2를 하면 카드뭉치N의 mid index를 찾을 수 있다.

이 mid index의 위치를 바꿔 가며 target을 찾아가는 풀이법으로,
찾으려는 target이 mid 보다 좌측에 있다면 더이상 mid의 우측을 볼 필요가 없으므로 right를 mid - 1로,
찾으려는 target이 mid 보다 우측에 있다면 더이상 mid의 좌측을 볼 필요가 없으므로 left를 mid + 1로 수정해주며 값을 찾으면 반환해주면 된다.

오름차순 정렬 돼 있지 않은 배열에서의 이진탐색은 조건이 더 붙어야한다.
아직까지 while문을 쓰고 그 안에 조건문을 넣는 게 익숙치 않은데, 이런 기본 케이스의 문제들 부터 익숙해져봐야겠다.

+ 백준 문제들을 풀며 BufferdReader나 BufferdWriter 등의 쓰임도 익숙해져야겠다.