[백준/자바] 20551번 Sort 마스터 배지훈의 후계자

 

 

 

문제

 

 

 

 

 

 

 

풀이

 

핵심은 이분 탐색을 이용하여 푼다는 것이다. 

찾고자 하는 수 중 가장 앞의 인덱스를 찾아야 하므로 기존 이분 탐색 로직에 아래 코드를 추가한다.

if (arr[mid] == x) {
    answer = mid; // x를 찾았다면 위치를 업데이트
    rt = mid - 1; // 더 왼쪽에 같은 값이 존재하는지 확인하기 위해 오른쪽 경계 줄이기
}

 

 

 

 

 

코드

package baekjoon._20551;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static int solution(int [] arr, int x) {

        int answer = -1;
        int lt = 0, rt = arr.length-1;

        while(lt <= rt) {

            int mid = (lt + rt) / 2;

            if (arr[mid] == x) {
                answer = mid; // x를 찾았다면 위치를 업데이트
                rt = mid - 1; // 더 왼쪽에 같은 값이 존재하는지 확인하기 위해 오른쪽 경계 줄이기
            }
            else if (arr[mid] < x) {
                lt = mid + 1;
            }
            else {
                rt = mid - 1;
            }

        }

        return answer;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 원소의 개수
        int M = Integer.parseInt(st.nextToken()); // 질문의 개수

        int [] a = new int[N];

        // 배열 입력받기
        for(int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(a);


        // 질문 받기
        for(int i= 0; i < M; i++) {
            int x = Integer.parseInt(br.readLine());
            sb.append(solution(a, x)).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();

        bw.close();
        br.close();




    }
}

 

 

 

이분 탐색에 익숙하지 않아 코드를 외워서 작성한 경향이 있다. 그래서 while(lt <= rt) 에서, = 가 들어가야 하는 이유를 몰랐는데, 이번 문제를 풀면서 알게 되었다. lt와 rt가 같은 경우에도 루프 내의 로직이 실행된다. 이는 lt와 rt가 동일한 위치에 있을 때 그 위치의 값을 검사할 수 있다는 것을 의미하며, 배열의 모든 위치를 정확히 검사할 수 있다.