코드업(Codeup) 3004 : 데이터 재정렬

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int cnt = sc.nextInt();
        int[] numsInfors = new int[cnt];
        for(int i = 0; i < cnt; i++) {
            numsInfors[i] = sc.nextInt();
        }

        int[] numsInfors_backup = Arrays.copyOf(numsInfors, cnt);
        quickSort(numsInfors);

        for(int i = 0; i < cnt; i++) {
            int value = binarySearch1(numsInfors, numsInfors_backup[i], 0, cnt);
            System.out.printf("%d ", value);
        }

    }

    public static void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        while (low <= high) {
            while (arr[low] < pivot) low++;
            while (arr[high] > pivot) high--;
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static int binarySearch1(int[] arr, int key, int low, int high) {
        int mid;

        if(low <= high) {
            mid = (low + high) / 2;

            if(key == arr[mid]) { // 탐색 성공 
                return mid;
            } else if(key < arr[mid]) {
                return binarySearch1(arr, key ,low, mid-1); // 왼쪽 부분 탐색 
            } else {
                return binarySearch1(arr, key, mid+1, high); // 오른쪽 부분 탐색 
            }
        }

        return -1; // 탐색 실패 
    }
}