이것이 취업을 위한 코딩테스트다. Chapter03

그리디 알고리즘이 다 그런건 아니지만 이 챕터에서 보여준 예제들의 특징은 뭉터기로 잘라내는 법을 찾아내는 것.

import java.util.*;
public class main {
    public static void main(String[] args) {

        Solution s = new Solution();
        System.out.println("GridExample01: "+s.GridExample01(1260));
        System.out.println("GridExample01Guide: "+s.GridExample01Guide(1260));

        System.out.println("GridExample02_01: "+s.GridExample02_01(new int[]{5,8,3}, new int[]{2,4,5,4,6}));
        System.out.println("GridExample02_02: "+s.GridExample02_02(new int[]{5,8,3}, new int[]{2,4,5,4,6}));
        System.out.println("GridExample02Guide: "+s.GridExample02Guide(new int[]{5,8,3}, new int[]{2,4,5,4,6}));
        //02_01과 유사. 한번씩 덧셈을 하지 않고 뭉터기로 덧셈을 할 수 있는 조건을 찾아내는 것이 단축의 핵심
        System.out.println("GridExample02Guide02: "+s.GridExample02Guide(new int[]{5,8,3}, new int[]{2,4,5,4,6}));

        //03은 가이드와 직접 작성했던 것과 유사해서 가이드 생략
        System.out.println("GridExample03 val1: "+s.GridExample03(new int[][]{{3,1,2},{4,1,4}, {2,2,2}}));
        System.out.println("GridExample03 val2: "+s.GridExample03(new int[][]{{7,4,1,8},{3,3,3,4}}));


        System.out.println("GridExample04: "+s.GridExample04(25,5));
        //1씩 빼지 않고 나머지 차를 그대로 빼는 것이 핵심. k > n일 경우 빠지는 것도 중요.
        System.out.println("GridExample04Guide: "+s.GridExample04(25,5));
    }
}
class Solution {
    public int GridExample01(int n) {
        int n500 = n / 500;
        int n100 = (n%500) / 100;
        int n50 = (n%100) / 50;
        int n10 = (n%50) / 10;
        return n500+n100+n50+n10;
    }
    public int GridExample01Guide(int n) {
        int[] coin = new int[]{500,100,50,10};
        int count = 0;
        for(int c : coin) {
            count += n/c;
            n %= c;
        }
        return count;
    }
    public int GridExample02_01(int[] valid, int [] num) {
        Arrays.sort(num);
        int n = valid[0];
        int m = valid[1];
        int k = valid[2];
        int answer = 0;
        //수정부
        int p = 0;
        int first = num[num.length-1];
        int second = num[num.length-2];

        if(k > m)
            return m * first;

        if(k+1 <= m) {
            p = m/(k+1);
            m %= (k+1);
        }
        answer += p * (first * k + second);
        answer += m*first;
        return answer;
    }
    public int GridExample02_02(int[] valid, int [] num) {
        Arrays.sort(num);
        int n = valid[0];
        int m = valid[1];
        int k = valid[2];
        int answer = 0;
        int t = k;
        int i = num.length-1;
        while(m > 0) {
            if(t > 0) {
                answer += num[i];
                t--;
            }
            else {
                t = k;
                answer += num[i-1];
            }
            m--;
        }

        return answer;
    }
    public int GridExample02Guide(int[] valid, int [] num) {
        Arrays.sort(num);
        int answer = 0;
        int m = valid[1];
        int k = valid[2];
        int first = num[num.length-1];
        int second = num[num.length-2];
        while(true) {
            for(int t =0; t<k;t++) {
                if(m == 0)
                    break;
                answer += first;
                m--;
            }
            if(m == 0) {
                break;
            }
            answer += second;
            m--;
        }

        return answer;
    }
    public int GridExample02Guide02(int[] valid, int [] num) {
        Arrays.sort(num);
        int answer=0;
        int m = valid[1];
        int k = valid[2];
        int first = num[num.length-1];
        int second = num[num.length-2];

        int count = m / (k+1) * k;
        count += m % (k+1);
        answer += count * first;
        answer += (m-count) * second;
        return answer;
    }
    public int GridExample03(int[][] cards) {
        int answer = -1;
        for(int[] row : cards)
            Arrays.sort(row);
        for(int i = 0; i<cards.length;++i) {
            if(cards[i][0] > answer)
                answer = cards[i][0];
        }
        return answer;
    }
    public int GridExample04(int n, int k) {
        int answer = 0;

        while(n != 1) {
            if(n % k == 0) {
                n/=k;
                answer++;
            }
            else {
                n--;
                answer++;
            }
        }

        return answer;
    }
    public int GridExample04Guide(int n, int k) {
        int answer = 0;

        int target;
        while(true) {
            target = (n/k)*k;
            answer += (n - target);
            if(n < k) {
                break;
            }
            answer += 1;
            n /= k;
        }
        answer += (n-1);
        return answer;
    }
}