[문제해결을 위한 창의적 알고리즘] 제자리멀리뛰기 (고급, p220)
이 문제는 이분 탐색에 의한 결정문제이다. 이런 유형의 문제 해결 방법에 익숙하지 않다면 생각해 내기 굉장히 어려운 문제 유형이라는 생각이 든다. 코드를 잘 살펴보고 바로 작성할 수 있도록 익혀야 할 것 같다. 책에서 설명하고 있듯이 최대값의 최소값 구하기 등의 문제에 잘 적용할 수 있다.
책의 해설에서는 c의 알고리즘 라이브러리를 불러 쓰도록 되어 있으나, 여기서는 중급에서 소개한 퀵 정렬 코드를 이용하여 정렬을 구현하였다.
import java.util.Scanner;
public class JumpSol223 {
public static int n, d, m;
public static int[] S = new int[50001];
public static int ub = 1000000000;
public static int lb, L;
public static boolean f(int x){
int cnt=0;
int cur=S[0];
for (int i = 1; i < n+2; i++){
if (S[i]<cur+x)
cnt++;
else
cur=S[i];
}
return (cnt<=m && cur==d);
}
public static void swap(int a, int b){
int t = S[a];
S[a]=S[b];
S[b]=t;
return;
}
public static void quick_sort(int s, int e){
if (s<e){
int p=s, l=s+1, r=e;
while(l<=r){
while(l<=e && S[l]<=S[p])
l++;
while(r>=s+1 && S[r]>=S[p])
r--;
if (l<r)
swap(l,r);
}
swap(p,r);
quick_sort(s, r-1);
quick_sort(r+1,e);
}
return;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
d = sc.nextInt();
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++)
S[i]=sc.nextInt();
sc.close();
S[n]=0;
S[n+1]=d;
quick_sort(0, n+1);
while(lb<ub){
L=(lb+ub+1)/2;
if(f(L))
lb=L;
else
ub=L-1;
}
System.out.println(ub);
return;
}
}
Big O(nlogn): 퀵소트의 경우 최악의 경우 n*n이 될 수 있음
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/JumpSol223.java