1920번

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

이번 문제는 자료구조를 이용하는 이분탐색이다.

나는 이 문제를 반복문 대신 재귀적으로 접근해보았다.

그런데 여지껏 계속 N과M, 분할정복 등 결과값이 연속적으로 연결되는 방식의 재귀함수를 만들다가 이분탐색을 만들려고 하니 조금 미숙한 부분이 있었다.

그 부분은 return부분인데, 내가 계속 해오던 DFS나 분할정복 등은 return값들이 연관되어 있는 문제만 풀다가 풀려고 하니 return을 어떻게 처리해야할지 고민했었다.

간단한 해결책은 그냥 재귀함수의 호출을 return으로 하는 것이었다.

또한 stackoverflow가 떠서 어느것이 문제인가 생각했는데 원인은 start지점과 end지점이 교차한 후 계속 반복되어서 였다.

이 문제는 이분탐색 그 자체이기 때문에 자료구조를 공부한 사람이라면 누구나 원리는 알고 있을 것이다.

 

정답 코드는 아래와 같다.

package backjoon.b1920;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class b1920 {
    static ArrayList<Integer> arr;
    static ArrayList<Integer> samp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new ArrayList<>();

        for(int i=0; i<N; i++){
            arr.add(Integer.parseInt(st.nextToken()));
        }
        arr.sort(Integer::compareTo);
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        samp = new ArrayList<>();

        for(int i=0; i<M; i++){
            samp.add(Integer.parseInt(st.nextToken()));
        }
        StringBuilder sb = new StringBuilder();
        for(int i : samp){
            sb.append(binarySearch(i,0,arr.size()-1)).append("\n");
        }
        System.out.println(sb);
    }
    public static int binarySearch(int search, int start, int end){
        int mid = (start+end)/2;
        if(start<=end){
            if(search<arr.get(mid)){
                return binarySearch(search,start,mid-1);
            }
            else if(search>arr.get(mid)){
               return binarySearch(search,mid+1,end);
            }
            else if (search==arr.get(mid)) {
                return 1;
            }
        }
        return 0;
    }
}