[TopCoder] 초급 - 시뮬레이션

 오늘 초급부터 시작을 해보겠습니다. 초급 단계는 누가봐도 쉽다고 느낄 만큼 쉬운 문제입니다.

일단 문제를 보겠습니다.

  문제

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

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

지금 타로는 병에 키위 주스를 재분배하려고 하며, 0 부터 M-1까지 M 회 조작합니다. i 번째의 조작은 타로가 병 fromId[i] 부터 병 toId[i]에 키위 주스를 넣는 것을 의미합니다. 병 fromId[i] 가 비어 있거나 병 toId[i]가 꽉 차 있는 순간, 타로는 더 이상 키위 주스를 넣지 않습니다. M개의 요소를 가진 정수 배열 int[]를 리런해주세요 배열의 i 번째 요소는 모든 주스를 쏟는 작업이 완료되고 i 번째 병에 남아 있는 키위 주스의 양입니다.

  이해 

문제를 이해하는데 시간이 좀 걸렸습니다. 영어로 되어 있는 것을 풀어서 써놔서 입력 데이터와 출력 데이터를 좀 보고 문제를 완벽하게 이해할 수 있었습니다.

capacities = { 20, 20 }

bottles = {5 , 8 }

fromId = { 0 }

toId = { 1 }

결과 값 : { 0 . 13 }

즉 capacities는 최대 담을 수 있는 병의 용량이고 bottles는 현재 병에 담겨 있는 주스의 양입니다. 그리고 from 과 to 는 배열 주소라고 생각하시면 되겠습니다. 다시 말해 bottles[0] 을 bottles[1] 에 넣어라는 말입니다.

책에서는 3단계를 나눠서 코딩을 했습니다. 그냥 순서에 맞게 문제 순서에 맞춰서 코드를 작성했고 점차 필요 없는 구문을 없애 나갔습니다. 저는 1단계 방법으로 처음으로 작성을 했습니다.

  코드

public static int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId) {
 
        for (int i = 0; i < fromId.length; i++) {
            int from = fromId[i];
            int to = toId[i];
 
            int result = bottles[from] + bottles[to];
 
            if (result > capacities[to]) {
                bottles[from] = result - capacities[to];
                bottles[to] = capacities[to];
            } else {
                bottles[from] = 0;
                bottles[to] = result;
            }
        }

처음에는 이렇게 작성을 했고 책에서 준 힌트를 보고 다시 작성을 했습니다.

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

좀 더 간단하게 작성을 했습니다.

여기에서 중요시 하는 것은 문제를 이해하고 손으로 한번 풀어보라는 것입니다.

바로 코딩을 하게 된다면 놓치는 부분도 많고 오래 걸리니 일단 손으로 작성을 하고 코딩 작성을 추천하고 있습니다.

또한 조건문을 최대한 적게 사용하여 버그를 줄이라는 말을 하고 있습니다.

위에 코드는 책에 내용이 아닙니다. 제가 짠 것을 올린 것이니 책과 다릅니다.

(출처 : 탑코더 레드를 찍어라! - Topcoder 알고리즘 트레이닝)