[JAVA/백준] 1920번 : 수 찾기

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

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

<Output>

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

 

<examples>
-입력

5
4 1 5 2 3
5
1 3 7 9 5

-출력

1
1
0
0
1

 

[풀이]

package Baekjoon;
import java.util.*;
public class P1920_수찾기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int A[] = new int[N];
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
        }

        //찾을 대상이 되는 배열 A 선 정렬
        Arrays.sort(A);//기본 : 오름차 순 정렬


        int M = sc.nextInt();
        for(int i=0;i<M;i++){
            boolean find = false;
            int s = sc.nextInt();
            int start = 0;
            int end = N-1;
            while (start<=end){
                int mid = (start+end)/2; // start, end값이 계속 업데이트 되므로, 유동적인 mid값을 설정
                int midV = A[mid];
                if(midV>s){
                    end = mid-1;
                }else if(midV<s){
                    start = mid+1;
                }else{ //A배열은 정렬되었다는 전체가 있어 가능한 알고리즘. 탐색하다보면 없는 값은 시작 값 == 끝 값이 됩니당
                    find = true;
                    break;
                }
            }
            if (find){
                System.out.println(1);
            }else {
                System.out.println(0);
            }
        }


    }
}

---

 

이진 탐색을 이용한 문제이다.

이진 탐색은

-데이터가 정렬 된 것을 전제로 하며,

-O(nlogn)의 시간 복잡도를 가진다.

-<포인터 탐색> mid 포인터를 기준으로 start, end 포인터를 조정하는 과정

 

즉, 시작값과 끝 값, 중앙값을 유동적으로 포인터로 지정해가며

찾고자하는 값을 탐색해간다.

물론 오름차 순 정렬 된 상태라는 게 전제.

 

탐색에서의 포인터 사용법에 익숙해지는 게 좋을 것 같다.

 

개인적으로 이 문제를 풀면서 처음으로

알고리즘이 기술이라고 느껴졌다.

해당 알고리즘을 이용해서 문제를 풀어

시간 복잡도가 O(nlogn)까지 축소가 가능하다는 게 새삼 신기했고

이론으로 공부해 온 알고리즘이 코드로 이렇게 풀어져서

효율적으로 결과를 낸다는 게 매력적이게 느껴졌다.

 

마냥 달달 외워서 문제를 풀기보다

생각하면서 이리 저리 해결하는 연습을 자주 해보자.