[정렬] 8. 이분검색

<<풀이>>

 

-나의 풀이-

문제는 이분검색이라는 방식을 사용해서 하는 것 같지만 일단 이분 검색을 잘 모르기 때문에 다른 방식으로 풀어봤다.

Arrays.sort를 통해서 정렬 한 뒤에 for문을 돌려 같은 값이 나오면 그 인덱스 값을 반환하는 방식을 사용해서 구할 수 있었다.

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(int n, int m, int[] arr) {
        Arrays.sort(arr);
        for(int i = 0; i < n; i++) {
            if(arr[i] == m) return i + 1;
        }
        return -1;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr  = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m , arr));
    }
}

 

여기서 시간 복잡도를 생각한다면 break를 활용할 수도 있다.

 

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(int n, int m, int[] arr) {
        Arrays.sort(arr);
        int answer = 0;
        for(int i = 0; i < n; i++) {
            if(arr[i] == m) {
                 answer = i + 1;
                 break;
            }
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr  = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m , arr));
    }
}

 

 

-강사님 풀이-

 

강사님은 이분 검색을 활용해서 문제를 풀었다. 이분 검색이란 먼저 정렬을 한 뒤에, 가장 앞쪽 값을 lt로 마지막 값을 rt로 지정한 뒤에 

 

mid = lt + rt / 2 를 하고 그 인덱스에 위치한 값이 우리가 찾는 것이면 그대로 그값을 반환하고 return을 한다. 하지만 그게 아니고 구하려는 값이 

 

현재 위치의 값보다 더 큰 값이면 그 밑에 있는 쪽은 무시하고 위쪽을 검색한다. 즉, lt 값을 mid + 1로 바꿔준다.

 

반대이면 위쪽을 무시하고 아래쪽을 검색한다. 즉, rt값을 mid - 1 해준다.

 

그 과정을 lt <= rt 일 때 까지 해준다. 

 

import java.util.Arrays;
import java.util.Scanner;

class Main {
    private int solution(int n, int m, int[] arr) {
        int answer = 0;
        Arrays.sort(arr);
        int lt = 0, rt = n - 1;
        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(arr[mid] == m) {
                answer = mid + 1;
                break;
            }
            if(arr[mid] > m) rt = mid - 1;
            else lt = mid + 1;
        }
        return answer;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr  = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m , arr));
    }
}

 

이분 검색 방식으로 시간복잡도를 조금 더 줄일 수 있다.!!

 

오늘도 좋은 개념을 배우고 갑니다~!