2021. 6. 21. 14:54ใ๐ Algorithm/๐ช๐ป Python ๋ฌธ์ ํ์ด
๋ฌธ์ ์ค๋ช
ํ๋๋์คํฌ๋ ํ ๋ฒ์ ํ๋์ ์์ ๋ง ์ํํ ์ ์์ต๋๋ค. ๋์คํฌ ์ปจํธ๋กค๋ฌ๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ต๋๋ค. ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ์ฒ๋ฆฌํ๋ ๊ฒ์ ๋๋ค.
์๋ฅผ๋ค์ด
- 0ms ์์ ์ 3ms๊ฐ ์์๋๋ A์์ ์์ฒญ - 1ms ์์ ์ 9ms๊ฐ ์์๋๋ B์์ ์์ฒญ - 2ms ์์ ์ 6ms๊ฐ ์์๋๋ C์์ ์์ฒญ
์ ๊ฐ์ ์์ฒญ์ด ๋ค์ด์์ต๋๋ค. ์ด๋ฅผ ๊ทธ๋ฆผ์ผ๋ก ํํํ๋ฉด ์๋์ ๊ฐ์ต๋๋ค.
ํ ๋ฒ์ ํ๋์ ์์ฒญ๋ง์ ์ํํ ์ ์๊ธฐ ๋๋ฌธ์ ๊ฐ๊ฐ์ ์์ ์ ์์ฒญ๋ฐ์ ์์๋๋ก ์ฒ๋ฆฌํ๋ฉด ๋ค์๊ณผ ๊ฐ์ด ์ฒ๋ฆฌ ๋ฉ๋๋ค.
- A: 3ms ์์ ์ ์์ ์๋ฃ (์์ฒญ์์ ์ข ๋ฃ๊น์ง : 3ms) - B: 1ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 3ms ์์ ์ ์์ ์ ์์ํด์ 12ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 11ms) - C: 2ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 12ms ์์ ์ ์์ ์ ์์ํด์ 18ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 16ms)
์ด ๋ ๊ฐ ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ 10ms(= (3 + 11 + 16) / 3)๊ฐ ๋ฉ๋๋ค.
ํ์ง๋ง A → C → B ์์๋๋ก ์ฒ๋ฆฌํ๋ฉด
- A: 3ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 3ms) - C: 2ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 3ms ์์ ์ ์์ ์ ์์ํด์ 9ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 7ms) - B: 1ms๋ถํฐ ๋๊ธฐํ๋ค๊ฐ, 9ms ์์ ์ ์์ ์ ์์ํด์ 18ms ์์ ์ ์์ ์๋ฃ(์์ฒญ์์ ์ข ๋ฃ๊น์ง : 17ms)
์ด๋ ๊ฒ A → C → B์ ์์๋ก ์ฒ๋ฆฌํ๋ฉด ๊ฐ ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ 9ms(= (3 + 7 + 17) / 3)๊ฐ ๋ฉ๋๋ค.
๊ฐ ์์ ์ ๋ํด [์์ ์ด ์์ฒญ๋๋ ์์ , ์์ ์ ์์์๊ฐ]์ ๋ด์ 2์ฐจ์ ๋ฐฐ์ด jobs๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ ์์ฒญ๋ถํฐ ์ข ๋ฃ๊น์ง ๊ฑธ๋ฆฐ ์๊ฐ์ ํ๊ท ์ ๊ฐ์ฅ ์ค์ด๋ ๋ฐฉ๋ฒ์ผ๋ก ์ฒ๋ฆฌํ๋ฉด ํ๊ท ์ด ์ผ๋ง๊ฐ ๋๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์. (๋จ, ์์์ ์ดํ์ ์๋ ๋ฒ๋ฆฝ๋๋ค)
์ ํ ์ฌํญ
- jobs์ ๊ธธ์ด๋ 1 ์ด์ 500 ์ดํ์ ๋๋ค.
- jobs์ ๊ฐ ํ์ ํ๋์ ์์ ์ ๋ํ [์์ ์ด ์์ฒญ๋๋ ์์ , ์์ ์ ์์์๊ฐ] ์ ๋๋ค.
- ๊ฐ ์์ ์ ๋ํด ์์ ์ด ์์ฒญ๋๋ ์๊ฐ์ 0 ์ด์ 1,000 ์ดํ์ ๋๋ค.
- ๊ฐ ์์ ์ ๋ํด ์์ ์ ์์์๊ฐ์ 1 ์ด์ 1,000 ์ดํ์ ๋๋ค.
- ํ๋๋์คํฌ๊ฐ ์์ ์ ์ํํ๊ณ ์์ง ์์ ๋์๋ ๋จผ์ ์์ฒญ์ด ๋ค์ด์จ ์์ ๋ถํฐ ์ฒ๋ฆฌํฉ๋๋ค.
์ ์ถ๋ ฅ ์์
๋ฌธ์ ์ ์ฃผ์ด์ง ์์ ๊ฐ์ต๋๋ค.
- 0ms ์์ ์ 3ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
- 1ms ์์ ์ 9ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
- 2ms ์์ ์ 6ms ๊ฑธ๋ฆฌ๋ ์์ ์์ฒญ์ด ๋ค์ด์ต๋๋ค.
ํ์ด ๊ณผ์
์์ ์ด ๋ชจ๋ ์ฒ๋ฆฌ๋๋ ์๊ฐ์ ํ๊ท ์ ๊ฐ์ฅ ์ต์๋ก ๊ตฌํด์ผํ๊ธฐ ๋๋ฌธ์ ํ์ฌ์์ ์ ์ด ๋๊ธฐ์๊ฐ์ ๋ชจ๋ ๊ตฌํด์ค์ผํ๋ค.
jobs ๋ฆฌ์คํธ์ ์์ ์ด ์์ฒญ๋๋ ์๊ฐ์ด ์ ๋ ฌ์ด ๋์ด ๋ค์ด์ค์ง ์์ผ๋ฏ๋ก ์ ๋ ฌ์ ๋จผ์ ์์ผ์ค์ผํ๋ค!
ํ์ push ์, ์์ ์์ ์๊ฐ ๊ธฐ์ค์ผ๋ก ์ต์ํ์ ๊ตฌํ๊ธฐ ์ํด jobs์ ๊ฑฐ๊พธ๋ก heap์ ๋ฃ์ด์ฃผ์๋ค.
heap์ push ์กฐ๊ฑด์ผ๋ก start(์์ ์์์๊ฐ) ๋ณด๋ค ํฌ๊ณ now(ํ์ฌ ์๊ฐ)๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๊ฒฝ์ฐ๋ง heap์ ๋ฃ์ด์ฃผ์๋ค.
work์์ ์์ ์ด ์๋ ๊ฒฝ์ฐ๋ heap์์ ํ๋ ๊บผ๋ด์ด start๋ฅผ ํ์ฌ์๊ฐ์ผ๋ก now๋ฅผ ์์ ์ฒ๋ฆฌ์๊ฐ์ผ๋ก ๋ณ๊ฒฝํด์ฃผ์๋ค.
answer (์ ์ฒด ์์ ์๊ฐ)์ now(ํ์ฌ์๊ฐ + ์์ ์ฒ๋ฆฌ ์๊ฐ) ์์ current[1] (์์ ์์ฒญ ์๊ฐ) ์ ๋บ ๋ค ๋ํด์ฃผ์๋ค.
import heapq
from collections import deque
def solution(jobs):
answer, now, start = 0, 0, -1
work = []
jobs = list(sorted(jobs, key= lambda k : k[0]))
jobs = deque(jobs)
total_cnt = len(jobs)
while jobs or work:
while jobs and start < jobs[0][0] <= now:
w_time, w_access = jobs.popleft()
heapq.heappush(work, [w_access, w_time])
if work:
current = heapq.heappop(work)
start = now
now += current[0]
answer += (now - current[1])
else:
now += 1
return int(answer / total_cnt)
'๐ Algorithm > ๐ช๐ป Python ๋ฌธ์ ํ์ด' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Python - ํ๋ก๊ทธ๋๋จธ์ค Level2] JadenCase ๋ฌธ์์ด ๋ง๋ค๊ธฐ (0) | 2021.06.21 |
---|---|
[Python - ํ๋ก๊ทธ๋๋จธ์ค Level3] ๋ฒ ์คํธ ์จ๋ฒ (0) | 2021.05.28 |
[Python - ํ๋ก๊ทธ๋๋จธ์ค Level2] ์์ ์ฐพ๊ธฐ (0) | 2021.05.28 |