[백준] 1920. 수 찾기(Java)

문제

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

 

풀이

특정 값을 찾는 문제로 시간 복잡도를 고려하여 이분탐색 알고리즘을 활용해 문제를 해결했습니다.

 

입력 받은 수열을 배열에 넣고 정렬했습니다.

타겟 값을 찾기 위해 이분탐색을 진행했습니다.

• s = 0, e = N-1로 두었습니다.
• while 조건은 e ≥ s로 두었습니다.(e == s 때 리턴해주기 위해)

1. mid 값이 타겟값 보다 클 경우, (더 커질 필요가 없기 때문에) mid ~ e 까지의 후보군을 제외했습니다.
   • 이때 e = mid-1로 e값을 변경했습니다.
   • e = mid로 설정하면 s와 e가 같아지는 상황에서 무한루프에 걸리게 되면서 시간 초과가 발생합니다.
2. mid 값이 타겟값 보다 작을 경우, (더 작아질 필요가 없기 때문에) s ~ mid 까지의 후보군을 제외했습니다.
   • s = mid+1로 s값을 변경했습니다.
   • 마찬가지로, s = mid로 설정하면 s와 e가 같아지는 상황에서 시간 초과가 발생합니다.
3. mid값이 타겟값과 동일할 경우
   • 원하는 값을 찾았기 때문에 1을 리턴합니다.
4. 이외의 케이스는 값을 찾기 못했기 때문에 0을 리턴합니다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        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 ++)
            sb.append(bs(0, N-1, Integer.parseInt(st.nextToken()))).append("\n");

        System.out.print(sb);
    }

    private static int bs(int s, int e, int tgt) {
        int m;

        while(e >= s){
            m = (s + e) / 2;

            // tgt보다 값이 클 경우, m ~ e 범위를 후보군에서 제거함
            // 이때 e 값을 m으로하면 시간초과 발생 -> s와 e가 같아지면서 무한루프 때문
            if(arr[m] > tgt) e = m-1;
            // tgt보다 값이 작을 경우, s ~ m 범위를 후보군에서 제거함
            else if(arr[m] < tgt) s = m+1;
            else return 1;
        }

        return 0;
    }
}