๋ฌธ์ ์ค๋ช
๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด, ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๊ฐ [70kg, 50kg, 80kg, 50kg]์ด๊ณ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ด 100kg์ด๋ผ๋ฉด 2๋ฒ์งธ ์ฌ๋๊ณผ 4๋ฒ์งธ ์ฌ๋์ ๊ฐ์ด ํ ์ ์์ง๋ง 1๋ฒ์งธ ์ฌ๋๊ณผ 3๋ฒ์งธ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ 150kg์ด๋ฏ๋ก ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ ์ด๊ณผํ์ฌ ๊ฐ์ด ํ ์ ์์ต๋๋ค.
๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค.
์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ด์ ๋ฐฐ์ด people๊ณผ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ limit๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๊ธฐ ์ํด ํ์ํ ๊ตฌ๋ช ๋ณดํธ ๊ฐ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
์ ํ์ฌํญ
- ๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋์ 1๋ช ์ด์ 50,000๋ช ์ดํ์ ๋๋ค.
- ๊ฐ ์ฌ๋์ ๋ชธ๋ฌด๊ฒ๋ 40kg ์ด์ 240kg ์ดํ์ ๋๋ค.
- ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ 40kg ์ด์ 240kg ์ดํ์ ๋๋ค.
- ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ ํญ์ ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ ์ค ์ต๋๊ฐ๋ณด๋ค ํฌ๊ฒ ์ฃผ์ด์ง๋ฏ๋ก ์ฌ๋๋ค์ ๊ตฌ์ถํ ์ ์๋ ๊ฒฝ์ฐ๋ ์์ต๋๋ค.
์ ์ถ๋ ฅ ์
people | limit | return |
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
ํ์ด ์ฝ๋
def solution(people, limit):
answer = 0
people.sort()
left = 0
right = len(people)-1
while True:
if left > right:
break
if left == right:
answer += 1
break
new_limit = limit - people[left]
while right > 0 and people[right] > new_limit:
right -= 1
answer += 1
if left < right:
left += 1
right -= 1
answer += 1
return answer
๋ฌธ์ ๋ถ๋ฅ๋ ํ์๋ฒ์ด ๋ง๋ค.
ํ์ง๋ง ๊ตฌํํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ฑ์ ์ฌ์ฉํ๊ฑฐ๋, ํฌ ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํด์ ํ์ดํด์ผ ํ๋ ๊ฒ ๊ฐ๋ค.
level 2์ ๋ฌธ์ ๋ ์๋ ๊ฒ ๊ฐ์๋ฐ.. ์๊ทผํ ์ ๋จน์ ๋ฌธ์ ๋ค.
์ฐ์ ํ์๋ฒ์ธ ์ด์ ์ ๋ํด ์ค๋ช ํด๋ณด๋๋ก ํ๊ฒ ๋ค.
๋ณดํธ๋ 1๋ช ~2๋ช ๊น์ง ํ ์ ์๋ค. ๋ณดํธ๋ฅผ ํ์ธ ๋ ๊ฐ์ฅ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์, ์ต๋ํ limit์ ๊ทผ์ ํ๊ฒ ํ์ฐ๋ ๋ฐฉ์์ด ํจ์จ์ ์ผ ๊ฒ์ด๋ค.
๊ทธ๋ ๋ค๋ฉด, ์ฌ๋๋ค์ ๋ฌด๊ฒ๋ฅผ ์ ๋ ฌ์ ํ๊ณ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋ + ํ๊ณ๋ฅผ ๋์ง ์์ ๋งํผ์ ๋ฌด๊ฑฐ์ด ์ฌ๋์ ์กฐํฉ์ผ๋ก ํ์ฐ๋ ๊ฒ์ด ๊ฐ์ฅ ํจ์จ์ ์ผ ๊ฒ์ด๋ค.
ํ์๋ ํฌ ํฌ์ธํฐ ๋ฐฉ์์ผ๋ก ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ค.
left ํฌ์ธํฐ์ right ํฌ์ธํฐ๋ฅผ ๋ง๋ค์ด ๊ฐ๊ฐ people์ ์ ๋์ ๋๊ธฐ ํ๋๋ก ํ๋ค.
๊ตฌํ ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ๋ค.
1) left ํฌ์ธํฐ๊ฐ right ํฌ์ธํฐ๋ณด๋ค ์ปค์ง๋ฉด ์ด๋ฏธ ๋ชจ๋ ์ฌ๋์ ํ์ด ๊ฒ์ด๋ผ๊ณ ํ๋จ, break
2) left ํฌ์ธํฐ์ right ํฌ์ธํฐ๊ฐ ๊ฐ์ ์์น๋ผ๋ฉด, ์ด ์์น์ ์๋ ์ฌ๋ 1๋ช ๋ง์ด ๋จ์๋ค๊ณ ํ๋จ, answer += 1ํ break
3) new_limit์ ํ๊ณ์์ ํ์ฌ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋์ ๋ฌด๊ฒ๋ฅผ ๋บ ๊ฒ.
4) new_limit์ ๋์ง ์๋ ์ฌ๋๊น์ง right ํฌ์ธํฐ๋ฅผ ์์ผ๋ก ์ด๋, ๋๋ ์ฌ๋์ ์ด๋ค ์กฐํฉ์ผ๋ก๋ 2๋ช ์ ์กฐํฉ์ผ๋ก ํ์ธ ์ ์์ผ๋ฏ๋ก answer += 1, right ํฌ์ธํฐ๋ 0๋ณด๋ค ์์์ง๋ฉด ์ ๋๋ฏ๋ก ์กฐ๊ฑด ์ฝ์ ํ์.
5) left < right์ธ ๊ฒฝ์ฐ, ์๋ก ๋ค๋ฅธ ๋ ์ฌ๋์ ๊ฐ๋ฆฌํค๋ ๊ฒ์ด๋ฏ๋ก ๋ ์ฌ๋์ ์ ํํด์ ๋ณดํธ์ ํ์ฐ๋ฏ๋ก, left์ right ๋ชจ๋ ํ ์นธ์ฉ ์ด๋, answer += 1
์ด์ ์ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ผ๋ก๋ ๋ง์ด ์๋ํด๋ดค๋๋ฐ, ์๊ฐ ์ด๊ณผ์ ์ํฅ์ด ๋๋ฌด ์ปค์ ํฌ ํฌ์ธํฐ ๋ฐฉ์์ผ๋ก ํด๊ฒฐํ๋ ๊ฒ์ด ๊ฐ์ฅ ์ข์๋ค.
๋์ ๋ณธ ํ ์คํธ ์ผ์ด์ค๋ก ๋ ๊ฐ์ง๊ฐ ์๋ค.
1) [60], 70, 1
2) [60, 60], 60, 2
๊ฐ์ฅ ๊ธฐ๋ณธ์ ์ธ ๋ฐํ์ ์๋ฌ๋ฅผ ์ ๊ฑฐํ๊ธฐ ์ํ ์ข์ ํ ์คํธ ์ผ์ด์ค ๋ ๊ฐ์ด๋ฏ๋ก, ํน์ ๋ฐํ์ ์๋ฌ๊ฐ ๋ฌ๋ค๋ฉด ํ์ธํด๋ณด๊ธธ ๋ฐ๋๋ค.
'๐ ์ฝ๋ฉํ ์คํธ ๋๋น : PS' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ๋ฉ๋ฆฌ ๋ฐ๊ธฐ (level2, python) (0) | 2022.09.09 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] N๊ฐ์ ์ต์๊ณต๋ฐฐ์ (level2, python) (0) | 2022.09.09 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์ง์ง์ด ์ ๊ฑฐํ๊ธฐ (level2, python) (0) | 2022.09.08 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์์ด ๋๋ง์๊ธฐ (level2, python) (0) | 2022.09.08 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์นดํซ (level2, python) (0) | 2022.09.08 |