[백준 2024/01/24] 1920번 수 찾기

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

1920번: 수 찾기

 

1. 접근 방법

이번 문제는 시간 제한만 생각 안한다면, 브론즈 레벨까지 갈 수 있는 문제라고 생각했다.

그럼에도 불구하고, 정답 비율이 29.905% 인 것을 보아, 일반적으로 접근하면 안되겠다고 생각했다.

따라서 binary search를 적용해야겠다고 다짐했다.

 

binary search의 경우 이론적으로만 배웠었고,

직접 코드를 짜본적은 없던 것 같아서 바로 binary search 코드를 따올까 했지만,

이제는 알고리즘을 직접 짜봐야 되는 단계라고 생각하여, 틀리더라도 적어보자! 하면서 적기 시작했다. 

 

binary search의 경우 list를 오름차순 정렬하는 것 부터 시작한다.

이후 list의 중간 index 값과 x(존재 유무를 비교하고자 하는 수)와 비교한다. 

만약 같다면, 1을 출력하고 x의 값이 중간 index값보다 크다면,

mid+1 부터 오른쪽 끝까지 를 다시 기준으로 중간 index를 찾는다.

 

만약 작다면, 왼쪽 끝에서 부터 mid-1까지를 기준으로 다시 중간 index 값을 찾는다.

 

이후 다시 리뉴얼 된 mid 값과 x를 비교하고 같다면 1을 출력, 아니면 ... (반복)

 

rough draft

 

그래도 그럴싸하게 코드를 작성하여 문제에 넣어 돌려 봤지만, 시간 초과 판결을 받았다.

그래서 정석 binary search 코드와 비교해보았고, 나의 코드 일정 부분에서 문제점을 발견했다.

 

그래서 해당 부분을 수정하고 나니 맞힐 수 있었다.

 for이 아니라 while (l<=r)문을 사용한 것.

그리고 l, r = mid 가 아니라 l = mid+1, r = mid-1 인 부분을 놓쳤었다.

 

또한 chatGPT 가 (l+r)/2 가 아닌 l+(r-l)/2 를 제안해주었던 부분이 신기했다.

 l+r를 우회적으로 하도록 하여, 오버플로우 발생이 일어나지 않도록 돕는다.

이 부분이 신기했으며, 오랫동안 가져가고 싶은 개념이다.

 

2. 코드

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;

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

        int num1 = Integer.parseInt(reader.readLine());
        //String[] w_h = line.split("\\s+");


        int[] case1 = new int[num1];

        String[] line1 = reader.readLine().split("\\s+");

        for(int i = 0; i<num1; i++){
            case1[i] = Integer.parseInt(line1[i]);
        }

        Arrays.sort(case1);

        int num2 = Integer.parseInt(reader.readLine());
        String[] line2 = reader.readLine().split("\\s+");

        for(int i =0; i<num2; i++){
            int x = Integer.parseInt(line2[i]);
            System.out.println(hasit(x, case1));
        }

    }
    public static int hasit(int x, int[] case1){
        int l = 0;
        int r = case1.length -1;

        while(l<=r){
            int mid = l + (r-l)/2;
            //System.out.println(case1[mid]);
            //System.out.println(x);
            if(case1[mid]==x){
                return 1;
            }
            else if (case1[mid] < x){
                l = mid +1;
            }
            else{
                r=mid -1;
            }
        }
        return 0;
    }


}