[TopCoder 알고리즘] 시뮬레이션 - 키위주스

초기 상태와 어떤 작업을 수행할지를 제공하고, 그에 따라 최종 결과가 어떻게 될지 답하는 문제 유형

 

---

Problem : KiwiJuiceEasy

 

타로는 키위 주스를 준비했다. 타로는 0부터 N-1이라 이름을 붙인 N개의 병에 키위 주스를 넣었다. 이때 i번째 병의 용량은 capacities[i] 리터이며 타로가 i번째 병에 넣은 키위 주스의 양을 bottles[i] 리터라고 한다.

타로는 병에 키위주스를 재분배하려고 하며, 0부터 M-1까지 M회 조작한다. i번째의 조작은 타로가 병 fromId[i]부터 병 toId[i]에 키위주스를 넣는 것을 의미한다. 병 fromId[i]가 비어있거나 병 toId[i]가 꽉 차 있는 순간, 타로는 더 이상 키위주스를 넣지 않는다. 

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

 

 

 

제약 조건 :

 

capacities : 2-50개의 요소가 있는 배열로, 각 요소는 1~1000000 사이의 값을 갖는다

bottles : capacities와 같은 수의 요소가 있는 배열

fromId : 1-50개의 요소가 있는 배열

toId : fromId와 같은 수의 요소가 있는 배열

 

 

예시 :

 

capacities = {20 , 20}

bottles = {5 , 8}

fromId = {0}

toId = {1}

 

Returns : {0 , 13}

 

---

문제 해설

fromId와 toId에 주어진 병 번호에 따라 순차적으로 주스를 옮겨가는 코드를 작성하면 된다.

 

이때 주스를 옮기는 작업은 두 가지 경우의 수가 존재한다.

① 주스를 모두 옮길 수 있어 넘치지 않고 전부 옮기는 경우

② 옮길 주스의 양이 기존 주스 병의 남은 용량보다 많아 다 옮길 수 없는 경우

 

 

단순하게 생각하면 toId에 해당하는 병에 남은 용량을 옮길 주스의 양(fromId)과 비교해보고,

 

> if 남은 용량이 옮길 양보다 크면 then 주스를 모두 옮기고

> if 남은 용량이 옮길 양보다 적으면 then 옮길 수 있는 만큼만 옮기도록 코드를 구성하면 된다.

 

 

하지만 조건문이 필요 이상으로 많아지만 코드의 양이 많아지고 입력에 따라 처리되지 않는 부분이 발생할 수 있다.

이 경우에는 최솟값 함수를 사용하면 보다 간단하게 코드를 구현할 수 있다.

 

 

즉, 

 1) a에서 b 병으로 옮길 수 있는 주스의 양 move_amount = min( a병에 들어 있던 주스 양 , b병에 담을 수 있는 양) 

 2) a 병에서 move_amount 만큼을 빼기

 3) b 병에 move amount 만큼 더하기

 

이 과정을 fromId와 toId 리스트에 있는 모든 요소에 대해 수행하면 시뮬레이션 문제를 풀 수 있다.

---

Python

def KiwiJuiceEasy(capacities, bottles, fromId, toId):
  for i, from_id in enumerate(fromId):
    to_id = toId[i]
 
    move_amount = min(capacities[to_id] - bottles[to_id] , bottles[from_id])
    bottles[from_id] -= move_amount
    bottles[to_id] += move_amount
    
  return bottles

 

line 2 : enumerate는 fromId 리스트로부터 각각 index, value를 가지고 온다

line 5 : from_id 병에 들어있는 주스의 양과 to_id의 남은 용량의 최솟값이 옮길 주스의 양이 된다

line 6 : 위에서 구한 move_amount를 from_id 병에서 뺀다

line 7 : move_amount를 to_id 병에 더한다

line 9 : for loop가 끝나고 결과를 리턴한다

 

 

Test Case 실행 예시 :

 

 

 

출처 : TopCoder 알고리즘 트레이닝, 타카하시 나오히로 지음

본 포스팅은 [TopCoder 알고리즘 트레이닝] 책의 내용을 바탕으로 Python 코딩한 내용입니다.

---