[백준] 1920번 수 찾기 - 이진 탐색 알고리즘/ 함수 이용(재귀X)

문제

 

My Code

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] A;
    static int resultNum;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        A = new int[n];

        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < n; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);


        int m = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[m];
        int[] result = new int[m];

        for (int j = 0; j < m; j++){
            int index = A.length/2;
            arr[j] = Integer.parseInt(st.nextToken());
            two(index, arr[j]);
            result[j] = resultNum;
        }

        for (int a:result) {
            System.out.println(a);
        }
    }

    private static void two(int index, int var) {
        if(A[index] > var){
            if (index == 0) {
                resultNum = 0;
                return;
            }
            index = index/2;
            two(index, var);
        }
        else if(A[index] < var){
            if(index >= A.length-1) {
                resultNum = 0;
                return;
            }
            index = (index + A.length)/2;
            two(index, var);
        }
        else {
            resultNum = 1;
            return;
        }
    }
}

 

 

문제의 핵심 & 알게된 점

오름차순으로 정렬시킨 배열을 이진 탐색 알고리즘을 이용해 

중간값과 비교해사며 존재 여부를 체크해야 한다.

 

시간제한이 1초이다보니 위의 코드처럼 재귀함수가 아닌 형태로 이진 탐색을 구현해야한다.

재귀함수는 스택을 이용한 방식이라 메모리를 많이 차지하기 때문이다.

 

위의 two()함수를 void형이 아닌 int형으로 하여 return값을 얻고 싶었으나 

if문에서 return값을 넣으니 모든 조건에서 return이 되지 않아 오류가 떠서

결국 void형으로 바꾸었다.

하지만 수정한 Code처럼 while문으로 감싸고 if문에 return을 하고

안 감싸진 부분은 return 0;으로 하여 오류가 없도록 구현했다.

 

 

수정한 Code

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int[] A;
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());
        A = new int[n];

        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < n; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);

        int m = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        int[] arr = new int[m];
        int[] result = new int[m];

        for (int j = 0; j < m; j++){
            int index = A.length/2;
            arr[j] = Integer.parseInt(st.nextToken());
            result[j] = two(arr[j]);

        }

        for (int a:result) {
            System.out.println(a);
        }
    }

    private static int two(int var) {
        int left = 0;
        int right = A.length-1;
        while (left <= right){
            int mid = (left + right)/2;
            if (A[mid] == var){
                return 1;
            }
            else if(A[mid] < var){
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return 0;
    }
}

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA