[Python - ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค Level3] ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ

2021. 6. 21. 14:54ใ†๐Ÿ“š Algorithm/๐Ÿ’ช๐Ÿป Python ๋ฌธ์ œ ํ’€์ด

๋ฐ˜์‘ํ˜•

 

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ

ํ•˜๋“œ๋””์Šคํฌ๋Š” ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์˜ ์ž‘์—…๋งŒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์ผ๋ฐ˜์ ์ธ ๋ฐฉ๋ฒ•์€ ์š”์ฒญ์ด ๋“ค์–ด์˜จ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ

programmers.co.kr

๋ฌธ์ œ ์„ค๋ช…

ํ•˜๋“œ๋””์Šคํฌ๋Š” ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์˜ ์ž‘์—…๋งŒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์€ ์—ฌ๋Ÿฌ ๊ฐ€์ง€๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ์ผ๋ฐ˜์ ์ธ ๋ฐฉ๋ฒ•์€ ์š”์ฒญ์ด ๋“ค์–ด์˜จ ์ˆœ์„œ๋Œ€๋กœ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ๋“ค์–ด

- 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)

 

 

 

๋ฐ˜์‘ํ˜•