반응형
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; // 탐색 실패
}
}
반응형
'프로그래밍 > 코드업 일기' 카테고리의 다른 글
코드업(Codeup) 4041 : 숫자 다루기 (0) | 2023.08.10 |
---|---|
코드업(Codeup) 3702 : 파스칼의 삼각형 2 (0) | 2023.08.10 |
코드업(Codeup) 2634 : 거스름돈 II (0) | 2023.08.10 |
코드업(Codeup) 2631 : 보물 찾기 (0) | 2023.08.10 |
코드업(Codeup) 2628 : 케익 자르기 (0) | 2023.08.10 |