[백준 1920] 수 찾기 (JAVA)

백준 1920번 문제  - 수 찾기

1920번: 수 찾기

---

문제 분석

 

• N개의 배열 수를 입력 받고, M개의 배열에 있는지 확인하고 싶은 수를 입력 받는다.
• M개의 수가 N개의 배열의 존재하는지 판단 후 존재하면 1을 아니면 0을 출력한다.

---

 

해결 키 포인트

 

• Arrays.sort()로 배열 정렬
• 이진 탐색으로 해당 수가 존재하는지 확인

---

이진 탐색

 

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙 값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다.

 

알고리즘

 

1. 현재 데이터셋의 중앙값을 선택
2. 중앙값 > 타깃 데이터 일 때 : 중앙 값 기준으로 왼쪽 데이터 셋 선택
   중앙값 < 타깃 데이터 일 때 : 중앙 값 기준으로 오른쪽 데이터 셋 선택
3. 과정 1~2를 반복하다, 중앙값 == 타깃 데이터 일 때 : 탐색 종료

Do It! 알고리즘 코딩 테스트

 

 

---

코드

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

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // N개의 A 입력
        int A [] = new int[N];

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

        // A 정렬
        Arrays.sort(A);

        // M 입력
        int M = Integer.parseInt(br.readLine());

        // M개의 수 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++) {
            int num = Integer.parseInt(st.nextToken());

            // 이진탐색에 필요한 변수
            int pivot = N/2;
            int start = 0;
            int end = N;

            // 해당 변수가 존재하는지 확인하는 변수 (존재 할 경우 1, 아닐 경우 0)
            int isContain = 0;

            // num이 A 배열에 존재하는지 이진탐색으로 확인

            // 시작, 끝의 차이가 1보다 작아질 때까지 반복
            while(end - start > 1) {
                // 현재 index의 값이 num과 동일할 경우
                if(A[pivot] == num) {
                    isContain = 1;
                    break;
                }
                // 현재 index의 값이 num보다 클 경우
                else if(A[pivot] > num) {
                    end = pivot;
                }
                // 현재 index의 값이 num보다 작을 경우
                else {
                    start = pivot;
                }

                // 중앙 값 설정
                pivot = start + (end-start)/2;
            }

            // 해당 값이 num인지 확인
            if(A[pivot] == num) {
                isContain = 1;
            }

            System.out.println(isContain);
        }

    }
}