[Baekjoon] 1920 - 수 찾기

📝 문제

 

 

 

❗ 주의

이분탐색은 데이터가 정렬된 후에 탐색을 진행해야 함을 잊지 말자.

배열을 입력받고 정렬하는 과정 꼭 거치기.

 

 

 

🔑 풀이 과정

N, M의 최대범위가 10의 5승, 제한 시간이 1초(약 1억번연산. 10의 8승)이므로 단순 탐색만으로는 시간 초과

그러므로 이진탐색을 사용한다.

 

실수했던 부분들

① middle은 인덱스 값이라는 것.

arr[middle]을 입력받은 값과 비교해야 하는데, 처음에 middle과 입력 값을 비교하고 있었다.

② 이진탐색은 데이터가 정렬되어 있다는 가정하에 진행해야 한다는 점.

정렬을 하지 않고 바로 배열을 사용했더니 값이 원하는대로 나오지 않았다.

 

 

🔓 답안

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        //배열 입력받고 정렬하기
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        //찾는 정수들 입력받고 이진탐색 하기
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++){
            int t = Integer.parseInt(st.nextToken());
            int ans = 0;

            int start = 0;
            int end = N-1;
            int middle;

            while(start <= end){
                middle = (start + end) / 2;
                if(arr[middle] < t){
                    start = middle + 1;
                } else if(t < arr[middle]){
                    end = middle - 1;
                } else{
                    ans = 1;
                    break;
                }
            }

            bw.write(ans + "\n");
        }

        bw.flush();
        bw.close();
    }
}

 

 

 

🖤 알고리즘 분류

- 자료 구조

- 정렬

- 이분 탐색