99클럽 코테 스터디 19일차 TIL + 백준 20551 (Sort 마스터 배지훈의 후계자, java)

오늘의 학습 키워드

• 이분탐색

 

문제 탐색하기

 

문제 풀이 설계하기

이분 탐색으로 문제를 풀이하면 되는데 문제의 조건 중에서 질문에서 주어진 정수 D가 정렬된 배열 B에서 가장 먼저 등장한 위치를 출력해주면 된다는 조건으로 인해 이분탐색으로 답이 나왔을 때 그 앞의 원소 들중에서 다시한번 탐색을 진행해서 풀 수 있었습니다.

 

코드

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

public class Main {
    private static int[] questions;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");

        int N = Integer.parseInt(arr[0]);
        int M = Integer.parseInt(arr[1]);

        questions = new int[N];
        for(int i=0; i<N; i++){
            questions[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(questions);

        int[] answers = new int[M];
        for(int i=0; i<M; i++){
            int target = Integer.parseInt(br.readLine());
            answers[i] = binarySearch(0, questions.length-1, target);
        }

        for(int a : answers){
            System.out.println(a + "");
        }
    }

    private static int binarySearch(int left, int right, int target){
        if(left > right) return -1;

        int mid = (left + right)/2;
        if(target == questions[mid]){
            int result = binarySearch(left, mid-1, target);
            if(result != -1){
                return result;
            }else{
                return mid;
            }
        }else if(target > questions[mid]){
            return binarySearch(mid+1, right, target);
        }else {
            return binarySearch(left, mid-1, target);
        }
    }
}

 

오늘의 회고

오늘의 문제는 이분탐색으로 풀기는 했지만 앞의 원소들을 다시한번 이분탐색을 진행해야 했기에 다른 풀이 방법도 찾아봐야겠다고 생각했습니다.