프로그래머스 - 고득점 킷 : 기능개발

https://programmers.co.kr/learn/courses/30/lessons/42586

코딩테스트 연습 - 기능개발

생각하기

처음에는 각 진도 상황을 deque에 넣고 

계속 시간별로 for문을 돌면서 popleft 할 것들을 찾아보려했다

하지만 시간별로 가면 최대 100의 시간을  돌것이고 100개의 기능이 있다면 

100개의 기능들의 진도상황을 업데이트 해주어야 할것이다 -> O(100 * 100) = O(10000)

 

가장 앞에 있는 기능과 뒤에 기능들의 진도상태를 비교하여 때문에 너무 쓸데 없이 for 문을 많이 돈다고 생각했다

 

deque에 넣는 요소를 다르게 해야겠다는 생각을 했다

이미 각 기능의 진도 상황과 각 기능의 스피드가 이미 다 나와있기 때문에  

각 기능이 100% 완료까지의 day들을 넣기로 했다

 

그렇다면 시간 별로 최대 100의 시간을 for 문돌면서 각각의 진도상황을 업데이트하는 과정을 거치지 않아도 된다

바로 가장 앞에 있는 기능과 뒤에 있는 기능들의 진도상태를 비교하면 된다

 

구현하기

남은 day들을 큐에 넣은 후

가장 앞에 있는 기능과 함께 pop될 것들을 찾기 위해

즉, 가장 앞에 있는 기능의 day 보다 작거나 같은 것들을 묶기위해

가장 앞에 있는 기능의 day보다 큰것이 나올 때까지 count한다

 

해당 count 값을 answer에 넣어주고 

해당 count 만큼 popleft 해준다

 

유의점

만약 100% 완료까지 3%가 남았는데 속도가 10이라면

3 / 10 은 0이 되어서 0 days가 된다

0.3 같은 경우는 반올림해주어서 1 day로 카운트 해주어야 한다

import math

math.floor(3.14) // 3
math.ceil(3.14) // 4

math.floor(-3.14) // -4
math.ceil(-3.14) // -3

 

코드

from collections import deque
import math

def solution(progresses, speeds):
    # 100% 일때 배포 가능
    # 뒤에있는 기능이 100%가 되면 앞에 있는 기능 배포시 같이 배포
    
    q = deque()
    for i in range(len(progresses)):
        day = math.ceil((100-progresses[i]) / speeds[i])
        q.append(day)
        
    answer = []
    while q:
        pop_cnt = 1
        for j in range(1, len(q)):
            if q[0] >= q[j]:
                pop_cnt += 1
            else:
                break
                
        answer.append(pop_cnt)
        while pop_cnt:
            q.popleft()
            pop_cnt-=1

    return answer