ํ์ฝ๋ ์๊ณ ๋ฆฌ์ฆ ์ ๋ณต - 1. ํค์ ์ฃผ์ค
๋ฌธ์
ํ๋ก๋ ๋ง์๋ ํค์ ์ฃผ์ค๋ฅผ ์ค๋นํ์ต๋๋ค.
ํ๋ก๋ 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๋ฒ์งธ ๋ณ์ ๋จ์ ์๋ ํค์ ์ฃผ์ค์ ์์
๋๋ค.
์ ์
class KiwiJuiceEasy:
def thePouring(self, capacities, bottles, fromId, told):
์ ๋ ฅ
capacities : 2~50๊ฐ์ ์์๊ฐ ์๋ ๋ฐฐ์ด, ๊ฐ ์์๋ 1 <= N <= 1000000
์ฌ์ด์ ๊ฐ์ ๊ฐ๋๋ค.
bottles : capacities์ ๊ฐ์ ์์ ์์๊ฐ ์๋ ๋ฐฐ์ด. bottles[i]๋ capacities[i]์ ๋ค์ด์๋ ์ฃผ์ค์ ์์ ์๋ฏธ
fromId : 1~50๊ฐ์ ์์๊ฐ ์๋ ๋ฐฐ์ด
toId : fromId์ ๊ฐ์ ์์ ์์๊ฐ ์๋ ๋ฐฐ์ด
์ถ๋ ฅ
๋ณ๋ค์ ๋จ์์๋ ์ฃผ์ค์ ์์ ๋ด๊ณ ์๋ ๋ฐฐ์ด
IO Example
# Case# 0
capacities = [20, 20]
bottles = [5, 8]
from_id = [0]
to_id = [1]
result : [0, 13]
# Case# 1
capacities = [10, 10]
bottles = [5, 8]
from_id = [0]
to_id = [1]
result : [3, 10]
# Case# 2
capacities = [30, 20, 10]
bottles = [10, 5, 5]
from_id = [0, 1, 2]
to_id = [1, 2, 0]
result : [10, 10, 0]
# Case# 3
capacities = [14, 35, 86, 58, 25, 62]
bottles = [6, 34, 27, 38, 9, 60]
from_id = [1, 2, 4, 5, 3, 3, 1, 0]
to_id = [0, 1, 2, 4, 2, 5, 3, 1]
result : [0, 14, 65, 35, 25, 35]
# Case# 4
capacities = [700000, 800000, 900000, 1000000]
bottles = [478478, 478478, 478478, 478478]
from_id = [2, 3, 2, 0, 1]
to_id = [0, 1, 1, 3, 2]
result : [0, 156956, 900000, 856956]
๊ตฌํ
1์ฐจ ์ฝ๋
1์ฐจ๋ก ์์ฑํ ์ฝ๋๋ ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋์ดํ๋ ค๊ณ ๋
ธ๋ ฅํ์๋ ๊ฒ ๊ฐ๋ค.
๋ชจ๋ 5๊ฐ์ ํ
์คํธ์ผ์ด์ค๋ ํต๊ณผํ์ง๋ง,
์กฐ๊ฑด๋ฌธ์ 4๊ฐ๋ ์ฌ์ฉํ๊ณ ์์
ํ์ ret๋ฐฐ์ด์ ์๋ก ๋ด๋ ๋ถํ์ํ ํ๋๊น์ง ํ๋ฉด์ ๋ฉ๋ชจ๋ฆฌ์ ์์ค์ฝ๋์ ๋๋
ํ๋ฅผ ์ ๋ฐํ ๊ฒ ๊ฐ๋ค.
class KiwiJuiceEasy:
def the_pouring(self, capacities, bottles, from_id, to_id):
ret = []
for i in range(len(from_id)):
from_i = from_id[i]
to_i = to_id[i]
# ์ฎ๊ธธ ๋ณ์ด ๋น์ด์์ผ๋ฉด pass
if bottles[from_i] == 0:
continue
# ๋ด๊ธธ ๋ณ์ด ๊ฝ์ฐจ์์ผ๋ฉด pass
if bottles[to_i] == capacities[to_i]:
continue
# ์ฎ๊ธธ ๋ณ์ ์ฉ๋๋ณด๋ค from + to์ ๋ด์ฉ๋ฌผ์ด ์ ๊ฑฐ๋ ๊ฐ์ผ๋ฉด
# bottles[to_i]์ ์ฃผ์ค๋ฅผ ์ฎ๊น.
if bottles[from_i] + bottles[to_i] <= capacities[to_i]:
bottles[to_i] += bottles[from_i]
bottles[from_i] = 0
# ์ฎ๊ธธ ๋ณ์ ์ฉ๋๋ณด๋ค from + to์ ๋ด์ฉ๋ฌผ์ด ๋ง์ผ๋ฉด
# bottles[to_i]์ ์ฃผ์ค๋ฅผ ์ฎ๊ธฐ๊ณ ๋๋จธ์ง๋ฅผ from์ ๋จ๊น.
elif bottles[from_i] + bottles[to_i] > capacities[to_i]:
tmp = bottles[to_i] + bottles[from_i] - capacities[to_i]
bottles[to_i] = capacities[to_i]
bottles[from_i] = tmp
# ๋ชจ๋ bottles๋ฅผ ret์ ๋ด์
for bottle in bottles:
ret.append(bottle)
return ret
2์ฐจ ์ฝ๋
2์ฐจ๋ก ์์ฑํ ์ฝ๋๋ ์กฐ๊ฑด๋ฌธ์ด ํ์์ด์์ผ๋ก ๋ง์ผ๋ฉด ์ฝ๋ ์์ด ๋์ด๋๊ณ ๋ฒ๊ทธ๋ฅผ ์ฐพ๊ธฐ ํ๋ค๊ฒ ๋๋ค.
์ด ๋ฌธ์ ์ ๊ฒฝ์ฐ if๋ฌธ์ minํจ์๋ก ๋์ฒดํ ์ ์์๋ค.
์ฎ๊ธธ ์ฃผ์ค์ ์๊ณผ ๊ธฐ์กด ์ฃผ์ค ๋ณ์ ๋จ์ ์ฉ๋์ ๋น๊ตํ์ฌ ์์ ๊ฒ์ด ์ด๋๋์ด ๋๊ธฐ ๋๋ฌธ์ด๋ค.
minํจ์๋ก ๋์ฒดํ๋ฉด์ ์กฐ๊ฑด๋ฌธ์ด ๊ฝค๋ ์ฌ๋ผ์ ธ์ ์ฝ๋์ ๊ฐ๋
์ฑ์ด ํจ์ฌ ์ข์์ก๋ค.
๊ทธ๋ฆฌ๊ณ ret ๋ฐฐ์ด์ ์ ๊ฑฐํ์ฌ ๋ฐ๋ก bottles ๋ฐฐ์ด์ returnํ๊ฒ๋ ํ์๋ค.
class KiwiJuiceEasy:
def the_pouring(self, capacities, bottles, from_id, to_id):
for i in range(len(from_id)):
f = from_id[i]
t = to_id[i]
# ์ฎ๊ธธ ์ฃผ์ค์ ์๊ณผ ๊ธฐ์กด ์ฃผ์ค ๋ณ์ ๋จ์ ์ฉ๋์ ๋น๊ตํด
# ์์ ๊ฒ์ด ์ด๋๋์ด ๋๋ค.
vol = min(bottles[f], capacities[t] - bottles[t])
# ์ฎ๊ธธ ์ฃผ์ค ๋ณ์ ์ด๋๋์ ๋บ๋ค.
bottles[f] -= vol
# ๊ธฐ์กด ์ฃผ์ค ๋ณ์ ๋จ์ ์ฉ๋์ ์ด๋๋์ ๋ํ๋ค.
bottles[t] += vol
return bottles
3์ฐจ ์ฝ๋
3์ฐจ๋ก ์์ฑํ ์ฝ๋๋ ๋ฐ๋ณต๋ฌธ ๋ด๋ถ์ ๋ก์ง์ด ๋ฌด๋ ค 3์ค์ด๋ค!!
์์๋ถ์ f์ t์ ๋ณ์ ์ ์ธ์ ์ ๊ฑฐํจ์ผ๋ก์จ ์์ฝ๋ฉ์ด ๋์์ง๋ง ๊ฐ๋
์ฑ๋ฉด์์ ์กฐ๊ธ ๋ถํธํด์ก๋ค๊ณ ๋๊ปด์ง๋ค.
ํ์ง๋ง ํ๋ก์ธ์ค๋ ๊ฝค๋ ์ฌํํ๋ค.
์ด๋๋์ ๋ฌด์ํ๊ณ ์ฎ๊ธธ ์ฃผ์ค์ ๊ธฐ์กด ์ฃผ์ค ์์ ์ดํฉ์ด ์ผ์ ํ๊ณ ,
์ฎ๊ธธ ์ฃผ์ค๋ ์ฃผ์ค ์ด๋๊ณผ ๊ธฐ์กด ์ฃผ์ค ๋ณ์ ์ฉ๋ ์ค์ ์์ ๊ฐ์ด ๋๋ค๋ ๊ฒ์ ์ด์ฉํ๊ธฐ๋ก ํ๋ค.
- ๊ธฐ์กด ์ฃผ์ค(bottles[to_id[i]]) : min(์ฎ๊ธธ ์ฃผ์ค + ๊ธฐ์กด ์ฃผ์ค, ๊ธฐ์กด ์ฃผ์ค ๋ณ์ ์ฉ๋)
- ์ฎ๊ธธ ์ฃผ์ค(bottles[from_id[i]]) : (์ฎ๊ธธ ์ฃผ์ค + ๊ธฐ์กด ์ฃผ์ค) - ๊ธฐ์กด ์ฃผ์ค
class KiwiJuiceEasy:
def the_pouring(self, capacities, bottles, from_id, to_id):
for i in range(len(from_id)):
sum = bottles[from_id[i]] + bottles[to_id[i]]
bottles[to_id[i]] = min(sum, capacities[to_id[i]])
bottles[from_id[i]] = sum - bottles[to_id[i]]
return bottles
๋ง๋ฌด๋ฆฌ
-
๋ฌธ์ ๋ฅผ ์ดํดํ๋ค๋ฉด ์์ผ๋ก ๊ณ์ฐํด๋ณด๊ธฐ. ๋จธ๋ฆฌ๋ก๋ง ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ค๊ณ ํ๋ฉด ํ๋ฉด์ ์ธ ๋ถ๋ถ๊น์ง ๋ฐ์ ์๊ฐํ์ง ๋ชปํจ.
์ฌ๋ฌ๊ฐ์ง ๊ฒฝ์ฐ์ ์๋ฅผ ์๊ฐํ๋ฉฐ ๋ฌธ์ ๋ฅผ ์ดํดํด๋ณด๊ธฐ. ์ด๋ป๊ฒ ์ฝ๋๋ฅผ ์์ฑํด์ผ๊ฒ ๋ค ์๊ฐ์ด ๋ค์ด๋ ๋๋ฝ๋ ๋ถ๋ถ์ด ์๋์ง ํ์ธํ๊ธฐ. -
์ฝ๋ฉ์ด ์ค๋ ๊ฑธ๋ฆฐ๋ค๋ฉด ๋ค์ ํ ๋ฒ ์์ผ๋ก ์๊ฐํด๋ณด๊ธฐ. ๋ง์ ๊ฒ์ ์๊ฐํ๊ณ ์ฝ๋๋ฅผ ์์ฑํด๋ ์์ํ์ง ๋ชปํ ๊ณณ์์ ๋ฌธ์ ๊ฐ ๋ฐ์ ํ ์ ์์.
์ด๋ด๋ ์ฝ๋ ์์ฑ์ ์ค๋จํ๊ณ ๋ฌธ์ ๋ฅผ ๋ค์ ์๊ฐํด๋ณด๊ธฐ. -
์กฐ๊ฑด๋ฌธ์ ๋๋๋ก ์กฐ๊ธ ์ฌ์ฉํ๊ธฐ. ๋ชจ๋ ๋ฌธ์ ๊ฐ Example์์ ๋ชจ๋ Testcase๋ฅผ ์ฃผ๋ ๊ฒ์ ์๋๊ธฐ ๋๋ฌธ์ ๊ฐ๋ฅํ ์กฐ๊ฑด๋ฌธ์ ์ ๊ฒ ์ฌ์ฉํด ๋ฒ๊ทธ๋ฅผ ์ค์ฌ์ผ ํ๋ค.