백준 20551번 Sort 마스터 배지훈의 후계자 Java

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

문제

---

생각하기

---

• 이분탐색 문제이다.
  • lowerBound 찾아야함

동작

같은 값 중에서 낮은 값을 찾아야 한다.

원래는 만들어진 Arrays.binarySearch() 사용했는데, 답이 나오긴 함, 근데 최적화가 안돼서 그런지 lowerBound문제라 시간이 너무 많이 걸려서 그냥 구현했다.

        if (arr[midIdx] == target) {
            // 타겟을 찾았으므로, 더 낮은 인덱스가 있는지 왼쪽을 계속 탐색합니다.
            int idx = binarySearch(low, midIdx - 1, target);
            if (idx != -1) {
                return idx;
            } else {
                return midIdx;
            }
        }

기존의 값을 찾았을 때도, 멈추지 않고, high를 midIdx - 1로 변경해서 계속 진행한다.

결과

코드

---

재귀

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        Arrays.sort(arr);
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(br.readLine());

            int ret = binarySearch(0, N - 1, num);
            sb.append(ret).append('\n');
        }


        return sb.toString();
    } // End of solve()

    private static int binarySearch(int low, int high, int target) {
        if (low > high) return -1;

        int midIdx = (low + high) / 2;

        if (arr[midIdx] == target) {
            // 타겟을 찾았으므로, 더 낮은 인덱스가 있는지 왼쪽을 계속 탐색합니다.
            int idx = binarySearch(low, midIdx - 1, target);
            if (idx != -1) {
                return idx;
            } else {
                return midIdx;
            }
        } else if (arr[midIdx] < target) {
            return binarySearch(midIdx + 1, high, target);
        } else {
            return binarySearch(low, midIdx - 1, target);
        }
    } // End of binarySearch()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
    } // End of input()
} // End of Main class

while

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] arr;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        Arrays.sort(arr);
        for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(br.readLine());

            int ret = binarySearch(0, N - 1, num);
            sb.append(ret).append('\n');
        }


        return sb.toString();
    } // End of solve()

    private static int binarySearch(int low, int high, int target) {
        int ret = -1;

        while (low <= high) {

            int midIdx = (low + high) / 2;
            if (arr[midIdx] == target) {
                ret = midIdx;          // 잠정적인 답으로 저장
                high = midIdx - 1;     // 왼쪽 절반을 계속 탐색
            } else if (arr[midIdx] < target) {
                low = midIdx + 1;
            } else {
                high = midIdx - 1;
            }
        }

        return ret;
    } // End of binarySearch()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
    } // End of input()
} // End of Main class