[백준] 1920 - 수찾기 JAVA 선형 탐색과 이진탐색의 차이

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

---

링크

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

문제

N개의 정수A [1], A [2], …, A [N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수A [1], A [2], …, A [N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

접근방법

 M개의 수가 각각 A배열 안에 포함되어 있는지, 확인을 하는 문제이다. 각 숫자들을 A배열 안에서 찾아야 하므로 '탐색'의 문제이다. 문제에서는 배열에서 특정 숫자를 탐색할 수 있는지 묻고 있다. 

 

풀이

 숫자를 찾기 위해 우리는 탐색 방법을 결정해야 한다. 선형 탐색으로 할 것인지, 아니면 이진 탐색으로 할 것인지 결정해야 한다. 문제에서 N의 최대는 100000 이므로 이진 탐색이 유리하다.(log2_100000) 이진 탐색에 대해서는 아래의 포스팅을 참고 바란다. 확실하게 선형과 이진의 차이점을 명시하기 위해 두 가지 방법으로 모두 풀었다.

 

 

[알고리즘] 이진 탐색(Binary Search) - 장점과 복잡도

 

1. 선형 탐색

 선형 탐색의 코드는 아래와 같다. A배열을 모두 입력받은 뒤, M개의 숫자를 입력받을 때마다, 선형 탐색을 진행한다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
            Main test = new Main();
    }

    public Main(){
        Scanner sc =new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();

        int[] a =new int[N];

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

        int M = sc.nextInt();

        int[] result = new int[M];
	//입력받자 마자 탐색 진행
        for (int i = 0 ; i < M ; i++){
            sb.append(check_contain(sc.nextInt(),a) ? 1 : 0);
            sb.append("\n");
        }

        System.out.println(sb);
    }

	//선형 탐색 후 값이 있는지 없는지 반환함
    public boolean check_contain(int num,int[] datas){
        boolean toggle = false;
        for (int data : datas){
        //찾으면 out
            if(data == num){
                toggle = true;
                break;
            }
        }

        return toggle;
    }
    
}

 

 

2. 이진 탐색

 이진 탐색을 위해 정렬을 시행한 뒤, 이진 탐색 메서드에 보낸다. 재귀 호출을 통해 찾는다면 1, 찾지 못한다면(시작점과 끝점이 교차되었을 때) 0 을 반환한다.

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

public class Main {

    public static void main(String[] args) {
            Main test = new Main();
    }

    public Main(){
        Scanner sc =new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        
        //N, A 입력
        int N = sc.nextInt();
        int[] A =new int[N];
        for (int i = 0 ; i < N ; i++){
            A[i]= sc.nextInt();
        }

        
        // 이진 탐색을 실행하기 위한 변수
        Arrays.sort(A);
        int start = 0;
        int end = N-1;


        //M 갯수 입력
        int M = sc.nextInt();
        for (int i = 0 ; i < M ; i++){

            int target = sc.nextInt();
            int answer =  binary_search(start,end,A,target);
            sb.append(answer);
            sb.append("\n");
        }

        System.out.println(sb);
    }
    
    
    //이진 탐색
    public int binary_search(int start,int end, int[] datas , int target){

        int mid = (start + end) / 2;

        
        //target과 같은 값을 찾을때는 1, 탐색을 해도 없으면 0 
        if(datas[mid] == target){
            return 1;
        } else if (start > end) {
            return 0;
        }

        
        //중앙값과 비교를 통해 양쪽 끝 조절
        if(datas[mid] < target){
            start = mid +1;
        }else{
            end = mid -1;
        }

        return binary_search(start, end, datas, target);

    }
}

 

결과

 

32448728 , 32448694 - 이진 탐색 결과

32448634 - 선형 탐색 결과

 

 탐색할 범위도 크고, 심지어 탐색 횟수도 많으니 약 2배에 달하는 차이가 눈에 보인다. 탐색 알고리즘의 효율을 극명하게 보여주는 문제였다고 생각한다. 탐색이 필요한 경우엔 꼭 탐색 알고리즘을 염두에 두자.

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.