[BOJ/JAVA] 20551번: 마스터 배지훈의 후계자

20551번: Sort 마스터 배지훈의 후계자

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

키워드

• 먼저 제자들에게 N개의 원소를 가진 배열A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다.

• 그 다음 M개의 질문을 한다.

• 제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력

• 단, D가 B에 존재하지 않는 경우에는 -1를 출력

---

구현

• 정렬 후 탐색이 이루어지므로, 입력값을 정렬할 필요가 있다.

• 중요한 것은 가장 먼저 등장한 위치를 출력이므로 이분탐색으로 찾더라도 가장 앞에 있는 원소를 찾아야 한다.

템플릿

low, high 모두 범위 안에 들어오도록 한다.

반복문의 속행 조건은 low≤high (항상 high가 low 이상이여야 한다.)

1. 해당 숫자를 찾은 경우
   • 가장 앞에 있는 원소를 찾아야 하므로, high==mid인 경우가 lowerBound이다.
   • 위 경우가 아니면 high=mid로 갱신한 뒤 반복문을 속행한다.

2. 해당 숫자보다 작은 경우
   • low 값을 mid+1로 해준다.

3. 해당 숫자보다 큰 경우
   • high 값을 mid-1로 해준다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class java20551 {
    // N : 원소의 개수
    // M : 질문의 개수
    static int N, M;

    static List<Integer> numberList;

    static int binarySearch(int targetNumber) {

        // low, high 둘 다 범위 안에 들어오게끔 설정
        int low = 0;
        int high = numberList.size() - 1;

        // 등호
        while (low <= high) {
            int mid = (low + high) / 2;

            if (numberList.get(mid) == targetNumber) {
                if (high == mid) {
                    return mid;
                }
                high = mid;
                continue;
            }

            // 더 작은 경우
            if (numberList.get(mid) < targetNumber) {
                low = mid + 1;
                continue;
            }

            // 더 큰 경우
            high = mid - 1;
        }

        return -1;
    }

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        numberList = new ArrayList<>();

        // 데이터 삽입
        for (int i = 0; i < N; i++) {
            numberList.add(Integer.parseInt(br.readLine()));
        }

        // 정렬
        Collections.sort(numberList);

        // 질문
        for (int i = 0; i < M; i++) {
            int targetNumber = Integer.parseInt(br.readLine());
            int result = binarySearch(targetNumber);
            System.out.println(result);
        }

        br.close();
    }
}

---

Uploaded by N2T