그리디 알고리즘이 다 그런건 아니지만 이 챕터에서 보여준 예제들의 특징은 뭉터기로 잘라내는 법을 찾아내는 것.
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;
}
}
'책(이것이 취업을 위한 코딩 테스트다)' 카테고리의 다른 글
| 이것이 취업을 위한 코딩테스트다. Chapter08 (0) | 2021.06.23 |
|---|---|
| 이것이 취업을 위한 코딩테스트다. Chapter07 (0) | 2021.06.20 |
| 이것이 취업을 위한 코딩테스트다. Chapter06 (0) | 2021.06.15 |
| 이것이 취업을 위한 코딩테스트다. Chapter05 (0) | 2021.06.13 |
| 이것이 취업을 위한 코딩테스트다. Chapter04 (0) | 2021.06.10 |