이분탐색) 백준_수 찾기

알고 넘어가야 할 이론:

원리는 이 영상에 잘 나와있어서 참고하면 좋을 듯 하다.

https://www.youtube.com/watch?v=HjtYYBsknX0 

---

오늘 공부한 내용

문제: 

백준 ) 수찾기

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

내가 생각한 문제풀이 : 

처음에는 첫번째 배열의 값을 정렬해준뒤, 두번째 배열의 값을 이중포문으로 하나하나 탐색하여 찾아주었다.

당연히 시간초과가 났고, 이진탐색에 대해 공부한 뒤 다시 풀어보았다.

 

정답코드:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

// 수찾기 (백준)
// https://www.acmicpc.net/problem/2745
public class Main {

    public ArrayList<Integer> solution(int[] arr, int n, int[] arr2, int b) {

        ArrayList<Integer> answer = new ArrayList<>();
        Arrays.sort(arr);


        for (int x : arr2) {
            int lp = 0;
            int rp = arr.length - 1;
            while (lp <= rp) {
                int mid = (lp + rp) / 2;
                if (x == arr[mid]) {
                    answer.add(1);
                    break;
                } else if (x < arr[mid]) {
                    rp = mid - 1;
                } else if (x > arr[mid]) {
                    lp = mid + 1;
                }

            }

            if(lp > rp){
                answer.add(0);
            }


        }


        return answer;
    }

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



        for (int x: t.solution(arr, n, arr2, m)) {
            System.out.println(x);
        }

    }
}

 

다른 사람의 문제풀이 : 

 

코드분석

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

public class Main { 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        int M = sc.nextInt();
        int[] arr2 = new int[M];
        for (int i = 0; i < M; i++) {
            arr2[i] = sc.nextInt();
        }
        Arrays.sort(arr);

        for (int i = 0; i < M; i++) {
            boolean result = search(arr, arr2[i], 0, arr.length - 1);

            if (result) {
                System.out.println(1);
            } else {
                System.out.println(0);
            }
        }



    }
    static boolean search(int[] arr, int target, int left, int right) {
        int mid;

        if (left <= right) {
            mid = (left + right) / 2;

            if (target == arr[mid]) {
                return true;
            } else if (target < arr[mid]) {
                return search(arr, target, left, mid - 1);
            } else {
                return search(arr, target, mid + 1, right);
            }
        }
        return false;
    }
}

 

똑같은 이진탐색 방법인데 재귀함수를 사용해서 풀었다. 메서드도 따로 빼주고...

재귀함수 몇번 도전해봤지만 자꾸 무한루프가 돌아서 잘 사용하지 않았었는데

다른 사람의 코드에서 재귀함수를 잘 활용한것을 보니 재귀함수도 어떻게 쓰는지 조금은 알 것 같다..

포인트는 재귀함수를 빠져나갈 수 있게 해주는 if문에 있구나 하고 깨닫는 코드였다.

---

더 공부할 내용

정렬할 때 Arrays.sort()를 사용해서 정렬했는데 

Arrays.sort()가 어떻게 구현되어있는지 궁금해서 따라가보니 

    /**
     * Sorts the specified range of the array using parallel merge
     * sort and/or Dual-Pivot Quicksort.
     *
     * To balance the faster splitting and parallelism of merge sort
     * with the faster element partitioning of Quicksort, ranges are
     * subdivided in tiers such that, if there is enough parallelism,
     * the four-way parallel merge is started, still ensuring enough
     * parallelism to process the partitions.
     *
     * @param a the array to be sorted
     * @param parallelism the parallelism level
     * @param low the index of the first element, inclusive, to be sorted
     * @param high the index of the last element, exclusive, to be sorted
     */
    static void sort(int[] a, int parallelism, int low, int high) {
        int size = high - low;

        if (parallelism > 1 && size > MIN_PARALLEL_SORT_SIZE) {
            int depth = getDepth(parallelism, size >> 12);
            int[] b = depth == 0 ? null : new int[size];
            new Sorter(null, a, b, low, size, low, depth).invoke();
        } else {
            sort(null, a, 0, low, high);
        }
    }

이렇게 구현되어 있었다.

클래스 이름은 Quicksort라고 되어있던데...

이게 그 알고리즘에서 말하는 퀵정렬방식 그건가...??

정렬방식에 선택정렬, 버블정렬, 삽입정렬, 퀵정렬 이 있던데

하나씩 더 공부해보면 좋을 것 같다.

---

느낀점

알고리즘이 예전에는 그냥 주먹구구식으로 풀었다면

요즘에는 알고리즘 개념에 대해 공부하고 그 개념과 관련된 문제들을 풀어보면서 공부하니까 

개념 이해도 잘 되고, 반복하나보니 그 알고리즘에 대해 빨리 습득할 수 있어서 공부할 맛이 난다

이해안되고 어떻게 구현해야할지 모를때는 막막하기만 한데 한번 깨달으면 그 뒤로 다른 문제들도 술술 문제가 풀려서 정말 재밌다.