KiwiJuice

오늘은 간단한 시뮬레이션 알고리즘 기초중 유명한 알고리즘인 키위주스 알고리즘을 풀어보도록 하겠습니다.

문제

타로는 맛있는 키위 주스를 준비했습니다.

타로는 맛있는 키위주스를 준비했습니다. 타로는 0부터 N-1이라 이름을 붙인 N개의 병에 키위주스를 넣었습니다. 

이때 i번째의 병의 용량은 capaties[i] 리터이며 타로가 i번째 병에 넣은 키위 주스의 양을 bottles[i] 리터라고 합니다.

타로는 병에 키위주스를 재분배하려고 하며, 0부터 M-1까지 M회 조작합니다.

i번째의 조작은 타로가 병 fromId[i]부터 병 toId[i]에 키위 주스를 넣는 것을 의미합니다. 

병 fromId[i]가 비어있거나 병 toId[i]가 꽉 차 있는 순간, 타로는 더 이상 키위 주스를 넣지 않습니다.

N개의 요소를 가진 정수 배열 int[]를 리턴해주세요. 배열의 i번째 요소는 모든 주스를 쏟는 작업이 완료되고 i번째 병에 남아 있는 키위 주스의 양입니다.

메소드는 public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId)

public in[] 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]];
            if (capacities[toId[i]] < sum) {
                bottles[fromId[i]] = sum - capacities[toId[i]];
                bottles[toId[i]] = capacities[toId[i]];
            } else {
                bottles[fromId[i]] = 0;
                bottles[toId[i]] = sum;
            }
        }
        return bottles;
}

위는 처음에 짰던 코드로 옮길 병의 크기가 옮길 주스의 총 양에 대한 조건분기를 코드로 작성하였습니다.

이 코드에서 if문의 조건 분기를 없애보면

public int[] refactorThePouring(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;
    }

이런 식의 코드가 나옵니다. 이 코드는 TopCoder 알고리즘 트레이닝에 나오는 코드로 이런식으로 리팩토링 또한 가능합니다.