TopCoder 문제로 연습해보는 알고리즘: 초급 (1) 시뮬레이션

TopCoder 알고리즘 트레이닝
https://book.naver.com/bookdb/book_detail.nhn?bid=7333164

TopCoder 알고리즘 트레이닝

4장 시뮬레이션 부분의 문제를 정리해 본 내용입니다.

 

---

 

 

KiwiJuice 

Problem

N bottles
capacities[0] ~ capacities[N-1]
bottles[0] ~ bottles[N-1]

redistribution
fromId[0] ~ fromId[M-1]
toId[0]~ toId[M-1]
-> fromId empty or toId full

return int[] of bottles[]

Example Data

0)
capacities = {20, 20}
bottles = {5, 8}
fromId = {0}
toId = {1}
Returns: {0, 13}

1)
capacities = {10, 10}
bottles = {5, 8}
fromId = {0}
toId = {1}
Returns: {3, 10}

2)
capacities = {30, 20, 10}
bottles = {10, 5, 5}
fromId = {0, 1, 2}
toId = {1, 2, 0}
Returns: {10, 10, 0}

3)
capacities = {14, 35, 86, 58, 25, 62}
bottles = {6, 34, 27, 38, 9, 60}
fromId = {1, 2, 4, 5, 3, 3, 1, 0}
toId = {0, 1, 2, 4, 2, 5, 3, 1}
Returns: {0, 14, 65, 35, 25, 35}

Solve

해결 방법

1.  fromId\[i\]와 toId\[i\]의 총량은 일정하다  
    \- int sum = bottles\[fromId\[i\]\] + bottles\[toId\[i\]\]

2.  재분배 후 toId\[i\]는 꽉 차거나 fromId\[i\]의 양을 더한 총량이다  
    \- bottles\[toId\[i\]\] = capcities\[toId\[i\]\] or sum

3.  fromId\[i\]에는 재분배 후 총량에서 toId\[i\]의 양을 제외한 만큼만 가지게 된다  
    \- bottles\[fromId\[i\]\] = sum - bottles\[toId\[i\]\]

자바 코드

public class KiwiJuice{
    public static int[] thePouring
                            (int[] capacities, int[] bottles, int[] fromId, int[] toId){

        int sum = 0;
        for (int i=0; i<fromId.length; i++){
            sum = bottles[fromId[i]]+bottles[toId[i]];
            bottles[toId[i]] = Math.min(capacities[toId[i]], sum);
            bottles[fromId[i]] = sum - bottles[toId[i]];
        }
        return bottles;
    }
}