[문제해결을 위한 창의적 알고리즘] 제자리멀리뛰기 (고급, 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

문제해결을 위한 창의적 알고리즘 목록