๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ ํ’€์ด/๊ตฌํ˜„

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]๊ณผ์ œ ์ง„ํ–‰ํ•˜๊ธฐ

by syLim___ 2023. 6. 17.
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/176962

 

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

์ฝ”๋“œ ์ค‘์‹ฌ์˜ ๊ฐœ๋ฐœ์ž ์ฑ„์šฉ. ์Šคํƒ ๊ธฐ๋ฐ˜์˜ ํฌ์ง€์…˜ ๋งค์นญ. ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์˜ ๊ฐœ๋ฐœ์ž ๋งž์ถคํ˜• ํ”„๋กœํ•„์„ ๋“ฑ๋กํ•˜๊ณ , ๋‚˜์™€ ๊ธฐ์ˆ  ๊ถํ•ฉ์ด ์ž˜ ๋งž๋Š” ๊ธฐ์—…๋“ค์„ ๋งค์นญ ๋ฐ›์œผ์„ธ์š”.

programmers.co.kr


์ฒ˜์Œ์— ๋ช‡๋ช‡ ํ…Œ์ผ€๋ฅผ ํ†ต๊ณผํ•˜์ง€ ๋ชปํ–ˆ๋Š”๋ฐ,

๋๋‚ด์ง€ ๋ชปํ•œ ๊ณผ์ œ๋ฅผ ํ์— ๋‹ค์‹œ ๋„ฃ์„๋•Œ cur_time์„ ์—…๋ฐ์ดํŠธํ•ด์ฃผ์ง€ ์•Š๊ณ  ๋„ฃ์—ˆ๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„๊ณ„์‚ฐ์ด ์ด์ƒํ•˜๊ฒŒ ๋˜์–ด์„œ์˜€๋‹ค.

๋˜, ํ•˜๋‹ค ๋ชปํ•œ ๊ณผ์ œ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ์ผ ๊ฒฝ์šฐ, ๊บผ๋‚ด๋Š” ์ˆœ์„œ๊ฐ€ FIFO์ธ์ค„ ์•Œ์•˜๋Š”๋ฐ ๋‹ค์‹œ ์ฝ์–ด๋ณด๋‹ˆ LIFO์˜€๋‹ค.

 

์ข€ ๋ณต์žกํ•˜์ง€๋งŒ ใ… 

์ •๋‹ต ํŒ์ •์„ ๋ฐ›์€ ์ฝ”๋“œ์ด๋‹ค.

from collections import deque
def solution(plans):
    answer = []
    plans = sorted(plans,key = lambda x : (x[1])) # ์‹œ๊ฐ„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ
    q = deque()
    n = len(plans)
    
    next = 1
    cur_time = plans[0][1]
    cur_task = plans[0]
    while len(answer) < n:
        ## 1. ํ•  ์ผ ์ •ํ•˜๊ธฐ
        if cur_time == plans[0][1]:
            pass
        # 1-1. ์ง€๊ธˆ์ด ๋‹ค์Œํ”Œ๋žœ ์‹œ์ž‘์‹œ๊ฐ„์ด๋ผ๋ฉด ๋ฐ”๋กœ ๋‹ค์Œํ”Œ๋žœ์„ ์‹œ์ž‘
        elif next < n and plans[next][1] == cur_time:
            cur_task = plans[next]
            next += 1
            
        # 1-2. ํ•˜๋‹ค ๋งŒ ๊ณผ์ œ๊ฐ€ ๋‚จ์•„ ์žˆ๋Š”์ง€ ํ์—์„œ ์ฒดํฌ
        elif len(q) > 0:
            if next >= n: # ๋‚จ์€ ๋‹ค์Œ ํ”Œ๋žœ์ด ์—†๋‹ค๋ฉด
                # ํ์— ์žˆ๋Š”๊ฑฐ ๋‹ค ์ˆ˜ํ–‰ ํ›„ ์ข…๋ฃŒ
                while q:
                    answer.append(q.pop()[0])
                break
            else:
                # ํ์—์„œ ๊บผ๋‚ธ ๊ณผ์ œ ์‹œ์ž‘
                cur_task = q.pop()
        
        # 1-3. ํ•˜๋˜ ๊ณผ์ œ๊ฐ€ ์—†๋‹ค๋ฉด, plans์—์„œ ๊บผ๋‚ธ ๊ณผ์ œ๋ฅผ ์‹œ์ž‘
        else:
            if next < n:
                cur_task = plans[next]
                next += 1

        ## 2. ํ˜„์žฌ ๊ณผ์ œ๊ฐ€ ๋๋‚˜๋Š” ์‹œ๊ฐ„ ๊ณ„์‚ฐํ•˜๊ธฐ
    
        # 2-1. ๋‹ค์Œ ํ”Œ๋žœ์ด ๋‚จ์•„ ์žˆ์ง€ ์•Š๋‹ค๋ฉด, ์‹œ๊ฐ„ ์ƒ๊ฐํ•˜์ง€ ์•Š๊ณ  ์ง„ํ–‰
        if next >= n:
            answer.append(cur_task[0])
            continue

        # 2-2. ์‹œ๊ฐ„ ๊ณ„์‚ฐ
        else:
            # ํ์—์„œ ๊บผ๋‚ธ ๊ณผ์ œ์— ๋Œ€ํ•ด, ํ˜„์žฌ์‹œ๊ฐ„ update
            if cur_time < cur_task[1]:
                cur_time = cur_task[1]
            # ์‹œ๊ฐ„ ๊ณ„์‚ฐ
            curh , curm = map(int,cur_time.split(":"))
            curm += int(cur_task[2])
            if curm >= 60:
                endh = curh + curm//60
                endm = curm%60
            else:
                endh = curh
                endm = curm
            
            ## 3. ๊ณผ์ œ๋ฅผ ๋๋‚ผ ์ˆ˜ ์žˆ๋Š”์ง€ ํŒ๋‹จ
            # 3-1. ํ˜„์žฌ ๊ณผ์ œ๋ฅผ ๋๋‚ผ ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ, ํ์— ๋„ฃ๊ณ  ํ˜„์žฌ ์‹œ๊ฐ„ update ํ•ด์ฃผ๊ธฐ
            if str(endh).zfill(2)+":"+str(endm).zfill(2) > plans[next][1]:
                h1, m1 = map(int,plans[next][1].split(":"))
                h2, m2 = map(int,cur_time.split(":"))
                temp = int(cur_task[2])-((h1*60+m1) - (h2*60+m2))
                cur_task[2] = str(temp)
                cur_time = plans[next][1] # cur time update
                q.append(cur_task)
            # 3-2. ํ˜„์žฌ ๊ณผ์ œ๋ฅผ ๋๋‚ผ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ, answer์— ๋„ฃ๊ณ  ํ˜„์žฌ์‹œ๊ฐ„ updateํ•ด์ฃผ๊ธฐ
            else:
                answer.append(cur_task[0])
                cur_time = str(endh).zfill(2)+":"+str(endm).zfill(2)
    
    
    return answer

 

์•… ์–ด์ง€๋Ÿฝ๋‹ค

 

์นœ๊ตฌ๋“คํ•˜๊ณ  ๋น„๊ตํ•ด๋ณด์•„๋„, ์ œ์ถœํ•œ ์‚ฌ๋žŒ๋“ค๊ณผ ๋น„๊ตํ•ด ๋ณด์•„๋„ ๋‚ด ์ฝ”๋“œ๊ฐ€ ์ข€ ๊ธด ํŽธ์ธ ๊ฒƒ ๊ฐ™์•„์„œ ์•ฝ๊ฐ„ ๋ฐ˜์„ฑ์„ ํ•˜๊ฒŒ ๋˜์—ˆ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ์ž๊พธ ์˜ค๋‹ต์ด ๋‚˜์˜ค๋Š” ์ด์œ ๋ฅผ ์ฐพ๊ธฐ๊นŒ์ง€๋„ ์ƒ๋‹นํžˆ ์‹œ๊ฐ„์ด ๊ฑธ๋ ค์„œ..

๋‹ค์Œ๋ถ€ํ„ฐ๋Š” ๋ฌธ์ œ ์—ด์‹ฌํžˆ ์ฝ๊ณ , ์ฝ”๋“œ๋ฅผ ์–ด๋–ป๊ฒŒ ์งค์ง€ ๊ตฌ์ƒ์„ ํƒ„ํƒ„ํžˆ ํ•ด๋†“๊ณ  ๋‚˜์„œ ์ฝ”๋“œ ์ž‘์„ฑ์„ ์‹œ์ž‘ํ•ด์•ผ๊ฒ ๋‹ค.

 

์ด ๋ฌธ์ œ๋Š” ํ•œ ๋ฒˆ ๋” ํ’€์–ด๋ด์•ผ๊ฒ ๋‹ค.

728x90