๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ย 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค.
๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค.
์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ด์ ๋ฐฐ์ด people๊ณผ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ limit๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๊ธฐ ์ํด ํ์ํ ๊ตฌ๋ช ๋ณดํธ ๊ฐ์์ ์ต์๊ฐ์ return
people | limit | return |
---|---|---|
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
์ฐ์ ์ฃผ์ด์ง people ๋ฐฐ์ด์ sortํ์ฌ ๋ชธ๋ฌด๊ฒ๊ฐ ์์ ์์ผ๋ก ์ ๋ ฌ๋๊ฒ ํ๋ค.
ํ ๊ตฌ๋ช ๋ณดํธ์ 2๋ช ๊น์ง๋ง ํ ์ ์์ผ๋ฏ๋ก, ๊ตฌ๋ช ๋ณดํธ์ ๋จผ์ ์ ์ผ ๋ฌด๊ฑฐ์ด ์ฌ๋์ ํ์ฐ๊ณ , ๊ทธ ๋ค์ ์ ์ผ ๊ฐ๋ฒผ์ด ์ฌ๋์ ํ์ด๋ค.
๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋๊ณผ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋์ด ๋ฌด๊ฒ ์ ํ์ ๋๊ธธ ๊ฒฝ์ฐ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋์ ํ์ฐ์ง ๋ชปํ๊ณ ๋์ด๊ฐ๋ค.
๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋์ ์์น๋ฅผ ํ์ํ๋ ์ธ๋ฑ์ค first์ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋์ ์์น๋ฅผ ํ์ํ๋ ์ธ๋ฑ์ค last๋ฅผ ์ค์ ํ๊ณ , ์ฌ๋์ ํ์ธ ๊ฒฝ์ฐ first++, lastโ ์ฒ๋ฆฌ ํ last์ first๊ฐ ๊ฐ์์ง๋ฉด ๊ทธ๋ง ๊ณ์ฐํ๋ค.
def solution(people, limit):
people.sort()
answer = 0
last=len(people)-1
# ๋ฌด๊ฑฐ์ด ์ฌ๋ ๋จผ์ ํ์ฐ๊ธฐ
first=0
while last-first>=0:
answer+=1
if people[last]+people[first]<=limit:
first+=1
last-=1
return answer
people ์ ๋ ฌ โ O(nlogn)
์ธ๋ฑ์ค, ๋ณ์ ์ ์ธ โ O(1)
while๋ฌธ โ O(n)