[do it 알고리즘] 백준 1920 (binary search)

이진 탐색이란?

• 정렬되 있는 배열에서 특정한 값을 찾아내는 알고리즘
• 배열의 중간값을 선택하여 찾고자 하는 X와 비교
• 중간값이 더 크면 좌측 데이터들을 대상으로 재탐색,  중간값이 더 작으면 우측 데이터들을 대상으로 재탐색
• 해당 값을 찾을 때까지 반복

문제 설명

 

풀기 전 생각

• 일반 반복문으로는 N = 100,000 M = 100,000이므로 N X M = 1억이 넘어가므로 1초만에 불가
• 앞서 배운 강의의 이진 탐색을 사용
• 자바 기본 정렬은 O(NlogN) + 이진 탐색은 O(NlogN)이므로 O(NlogN) 즉, 1초만에 해결 가능
• 재귀함수를 사용

코드

import java.util.*;
import java.io.*;
public class Baek1920 {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int [] arr = new int[N];
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++){  // 배열에 입력해주기
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 자바 기본 정렬
        st = new StringTokenizer(bf.readLine());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < M;i++){
            System.out.println(binarySearch(arr,0,arr.length-1,Integer.parseInt(st.nextToken())));
        }

    }
    public static int binarySearch(int[] arr,int start,int end,int findNum){
        int medianIndex = (start + end) / 2; // 중간값
        if (arr[medianIndex] == findNum) return 1; // 찾는 값과 같으면 1
        if (start == end) return 0; // 하나밖에 남지 않았는데 다르면 0
        if(arr[medianIndex] > findNum) { // 중간값이 더 크면 좌측 데이터
            return binarySearch(arr,start,medianIndex-1,findNum);
        }else{ // 중간값이 더 작으면 우측 데이터
            return binarySearch(arr,medianIndex+1,end,findNum);
        }
    }
}

오류 및 개선

• 예시 테스트케이스는 통과했지만 제출 시 stackOverflow
• 종료 조건에 문제가 있는 것이니 if(start >= end) return 0으로 고침
• 통과했으며 반례는 start = 0 , end = 1 일때 medianIndex = 0
• 중간값이 더 크면 start = 0, end = -1 이므로 start == end가 아니여서 무한 반복

최종 코드

import java.util.*;
import java.io.*;
public class Baek1920 {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int [] arr = new int[N];
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++){  // 배열에 입력해주기
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 자바 기본 정렬
        st = new StringTokenizer(bf.readLine());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < M;i++){
            System.out.println(binarySearch(arr,0,arr.length-1,Integer.parseInt(st.nextToken())));
        }

    }
    public static int binarySearch(int[] arr,int start,int end,int findNum){
        int medianIndex = (start + end) / 2; // 중간값
        if (arr[medianIndex] == findNum) return 1; // 찾는 값과 같으면 1
        if (start >= end) return 0; // 다르면 0
        if(arr[medianIndex] > findNum) { // 중간값이 더 크면 좌측 데이터
            return binarySearch(arr,start,medianIndex-1,findNum);
        }else{ // 중간값이 더 작으면 우측 데이터
            return binarySearch(arr,medianIndex+1,end,findNum);
        }
    }
}

강의 코드

import java.util.*;
import java.io.*;
public class Baek1920 {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(st.nextToken());
        int [] arr = new int[N];
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++){  // 배열에 입력해주기
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); // 자바 기본 정렬
        st = new StringTokenizer(bf.readLine());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        
        
        for(int i = 0; i < M;i++){
            boolean find = false;
            int target = Integer.parseInt(st.nextToken());
            int start = 0;
            int end = arr.length-1;
            
            while(start <= end){
                int midIndex = (start + end) / 2;
                int midValue = arr[midIndex];
                if(midValue > target){
                    end = midIndex-1;
                }else if(midValue < target){
                    start = midIndex + 1;
                }else{
                    find = true;
                    break;
                }
            }
            if(find){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
        }
    }
}

반복문 vs 재귀함수

 

	장점	단점
반복문	1. 흐름 파악이 쉽다	1. 반복 연산을 매번 새로 수행 2. 조건문 신경써야된다
재귀함수	1. 간단히 함수 호출로 반복 2. 이전 계산 결과 활용	1. 흐름파악 어려워 복잡도 계산 힘듬 2. 탈출 구문 신경 3. 오베헤드 큼