๐ ๋ฌธ์
https://programmers.co.kr/learn/courses/30/lessons/42627
๋ฌธ์ ์ค๋ช
ํ๋๋์คํฌ๋ ํ ๋ฒ์ ํ๋์ ์์ ๋ง ์ํํ ์ ์์ต๋๋ค. ๋์คํฌ ์ปจํธ๋กค๋ฌ๋ฅผ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ต๋๋ค. ๊ฐ์ฅ ์ผ๋ฐ์ ์ธ ๋ฐฉ๋ฒ์ ์์ฒญ์ด ๋ค์ด์จ ์์๋๋ก ์ฒ๋ฆฌํ๋ ๊ฒ์ ๋๋ค.
์๋ฅผ๋ค์ด
- 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 ์ดํ์ ๋๋ค.
- ํ๋๋์คํฌ๊ฐ ์์ ์ ์ํํ๊ณ ์์ง ์์ ๋์๋ ๋จผ์ ์์ฒญ์ด ๋ค์ด์จ ์์ ๋ถํฐ ์ฒ๋ฆฌํฉ๋๋ค.
โ๏ธ ํ์ด
์ ์ด ๋ฌธ์ , ํ์ด ๊ฐ๋ฅ์ ๋ชป ์ก์์ ์ด๋ ค์ ๋ค! (ใ ใ )
๐ก ํต์ฌ์ ์์ ์๊ฐ์ด ๊ฐ์ฅ ์ ์ ์์ ๋ถํฐ ์ฒ๋ฆฌํ๋ ๊ฒ์ด ํ๊ท ์ ์ค์ด๋ ๋ฐฉ๋ฒ์ด๋ผ๋ ๊ฒ์ด๋ค.
ํ๊ท ๊ฐ์ N๊ฐ์ ์์ ์ ์ํํ์ ๋, ๊ฐ ์์ ๋ค์ (๋๊ธฐ์๊ฐ+์์์๊ฐ)์ ๋ชจ๋ ๋ํ ๊ฐ์ N์ ๋๋ ๊ฒ์ด๋ค.
โ๏ธ ์์์๊ฐ์ด ์งง์ ์๋๋ก ์์ ์ ์ ๋ ฌํ๋ค.
โ๏ธ ์์์๋ถํฐ ์ฒ๋ฆฌํ ์ ์๋ ์์ (์์ ์ด ์์ฒญ๋ ์์ ์ด ํ์ฌ ๊ธฐ์ค์ผ๋ก ์ด์ ์ธ ๊ฒ)์ ์ฐพ๋๋ค. ์ฒ๋ฆฌํ ์ ์๋ ์์ ์ด๋ผ๋ฉด ๊ฐ์ฅ ๋จผ์ ๋ฐ๊ฒฌ๋ ๊ฒ์ด ์์์๊ฐ์ด ์ ์ผ ์งง์ ๊ฒ์ด๋ฏ๋ก, ์ด๋ฅผ ๋ฆฌ์คํธ์์ ๊บผ๋ธ๋ค. ํด๋น ์์ ์ ์ฒ๋ฆฌํ๋ค๋ ์๋ฏธ๋ก ํ์ฌ ์๊ฐ์ ์์ ์์์๊ฐ์ ๋ํด์ฃผ๊ณ , ํด๋น ์์ ์ (๋๊ธฐ์๊ฐ+์์์๊ฐ)์ ์ ๋ต ๋ณ์์ ๋ํ๋ค.
โ๏ธ ๋ชจ๋ ๋ฐฐ์ด์ ์์๋ฅผ ์ดํด๋ ํ์ฌ ์ฒ๋ฆฌํ ์ ์๋ ์์ ์ด ์๋ค๋ฉด ํ์ฌ ์๊ฐ์ 1์ ๋ํด์ฃผ๊ณ ๋ค์ ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ๋ณตํ๋ค.
โ๏ธ ๋ชจ๋ ์์ ์ ๋ค ์ดํ์ ๋, ์ ๋ต ๋ณ์๋ฅผ ์ด ์์ ์ ๊ฐ์๋ก ๋๋ ํ๊ท ๊ฐ์ ๊ตฌํ๋ค.
๐ป ์์ค์ฝ๋: ํ์ด์ฌ(Python)
import heapq
def solution(jobs):
answer = 0
time = 0
n = len(jobs)
# ์์์๊ฐ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ๋ค.
jobs = sorted(jobs, key=lambda x: x[1])
while jobs:
for i in range(len(jobs)):
if jobs[i][0]<=time: #์ํ๊ฐ๋ฅํ๋ฐ ์์์๊ฐ๋ ์ ์ผ ์งง๋ค๋ฉด ์ํํ๋ค
answer += (time-jobs[i][0]+jobs[i][1]) #๋๊ธฐ์๊ฐ+์ํ์๊ฐ
time += jobs[i][1]
jobs.pop(i)
break
if jobs and i==len(jobs)-1: time+=1 #ํ์ฌ ์ํํ ์ ์๋ ์์
์ด ์๋ฌด ๊ฒ๋ ์๋ค๋ฉด
return answer//n
jobs = [[0, 3], [1, 9], [2, 6]]
print(solution(jobs))
๐ ๐ ๐
๏ผฐ๏ฝ๏ฝ๏ฝ๏ฝ ๏ฝ ๏ผข๏ฝ ๏ผณ๏ผก๏ผน
๐๐ฉ๐ข๐ฏ๐ฌ๐ด ๐ง๐ฐ๐ณ ๐ณ๐ฆ๐ข๐ฅ๐ช๐ฏ๐จ