[Topcoder] 키위 주스

문제 출처 : 

1. 내가 짠 코드

public class test {
    public static void main(String[] args){
        test test = new test();
     /*   int[] cpapcities = {700000,800000,900000,1000000};
        int[] bottles = {478478,478478,478478,478478};
        int[] fromId = {2,3,2,0,1};
        int[] toId = {0,1,1,3,2};*/
       int[] cpapcities = {14,35,86,58,25,62};
        int[] bottles = {6,34,27,38,9,60};
        int[] fromId = {1,2,4,5,3,3,1,0};
        int[] toId = {0,1,2,4,2,5,3,1};
        int[] answer = test.thePouring(cpapcities,bottles,fromId,toId);
        for(int i=0; i<answer.length;i++){
            System.out.println(answer[i]);
        }
    }
    public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
        for(int i =0 ;i <fromId.length;i++) {
            int start = fromId[i];
            int remain = bottles[start];
            int to = toId[i];
            if(bottles[to]+remain >= capacities[to]){
                remain = remain - (capacities[to] - bottles[to]);
                bottles[to] = capacities[to];
            }
            else{
                bottles[to] = bottles[to] + remain;
                remain = 0;
            }
 
            bottles[start] = remain;
        }
 
        return bottles;
    }
 
}
 
 
----------------------------결과-------------------------------
0
14
65
35
25
35
 

2. 개선 코드 : Math.min 이용

- 옮길 주스의 양 vs 기존 주스 병의 남은 용량중에 min값이 이동량이 됨

-> 만약 옮길 주스의 양이 더 작다면 꽉 채우지 못한다는 것이므로 from의 남은양은 0

-> 기존 주스 병의 남은 용량이 더 작다면 꽉 채우고도 남는다는 뜻

public class test {
    public static void main(String[] args){
        test test = new test();
     /*   int[] cpapcities = {700000,800000,900000,1000000};
        int[] bottles = {478478,478478,478478,478478};
        int[] fromId = {2,3,2,0,1};
        int[] toId = {0,1,1,3,2};*/
       int[] cpapcities = {14,35,86,58,25,62};
        int[] bottles = {6,34,27,38,9,60};
        int[] fromId = {1,2,4,5,3,3,1,0};
        int[] toId = {0,1,2,4,2,5,3,1};
        int[] answer = test.thePouring(cpapcities,bottles,fromId,toId);
        for(int i=0; i<answer.length;i++){
            System.out.println(answer[i]);
        }
    }
    public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
        for(int i =0 ;i <fromId.length;i++) {
            int start = fromId[i];
            int to = toId[i];
 
            int vol = Math.min(bottles[start], capacities[to]-bottles[to]);
 
            bottles[start] = bottles[start]-vol;
            bottles[to] = bottles[to]+vol;
 
        }
 
        return bottles;
    }
 
}
 
 
----------------------------결과-------------------------------
0
14
65
35
25
35
 

3. 개선 코드 : 다음과 같은 규칙을 이용해 문제를 풀이

 - 두 주스의 총합은 항상 일정

 - to에 담겨질 용량은 두 주스의 총합 vs to의 capacities 중 작은 값이 들어가진다.

public class test {
    public static void main(String[] args){
        test test = new test();
     /*   int[] cpapcities = {700000,800000,900000,1000000};
        int[] bottles = {478478,478478,478478,478478};
        int[] fromId = {2,3,2,0,1};
        int[] toId = {0,1,1,3,2};*/
       int[] cpapcities = {14,35,86,58,25,62};
        int[] bottles = {6,34,27,38,9,60};
        int[] fromId = {1,2,4,5,3,3,1,0};
        int[] toId = {0,1,2,4,2,5,3,1};
        int[] answer = test.thePouring(cpapcities,bottles,fromId,toId);
        for(int i=0; i<answer.length;i++){
            System.out.println(answer[i]);
        }
    }
    public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId){
        for(int i =0 ;i <fromId.length;i++) {
            int sum = bottles[fromId[i]]+bottles[toId[i]];
            bottles[toId[i]] = Math.min(sum,capacities[toId[i]]);
            bottles[fromId[i]] = sum - bottles[toId[i]];
 
        }
 
        return bottles;
    }
 
}
 
 
----------------------------결과-------------------------------
0
14
65
35
25
35