[프로그래머스/Python] 기능개발

문제

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

프로그래머스

 

---

1. 큐 사용

 

남은 퍼센트 리스트에 저장

def solution(progresses, speeds):
    answer = []
    #몇 퍼센트 남았는지: 100-progresses
    percent = [100-i for i in progresses]

 

배포 가능 날짜 세기

percent : 남은 퍼센트

speeds : 하루에 끝낼 수 있는 퍼센트

percent // speeds 나머지가 있으면 +1 , 없으면 그대로

ex) 10퍼센트 남고 하루에 2퍼센트씩 할 수 있다면 5일이 걸림 (percent // speeds)

ex) 10퍼센트 남고 하루에 3퍼센트씩 할 수 있다면 4일이 걸림 (percent // speeds + 1)

    #percent // speeds 나머지 있으면 +1
    date = []
    for i in range(len(percent)):
        d = percent[i]//speeds[i]
        date.append(d if percent[i] % speeds[i] == 0 else d+1)

 

 

큐의 맨 앞(deploy)을 기준으로 더 작은 수이면(개발 완성 날짜가 빠름) cnt +=1, pop(0)

큰 수이면 deploy, cnt 재할당

    #새로운 배열에 날짜 담기 앞에 거 보다 날짜가 빠르면 같이 나감
    #다 없어질 때까지 +1
    cnt = 1
    deploy = date.pop(0)
    while len(date) > 0:
        if deploy >= date[0]:
            cnt+=1
            date.pop(0)
        else:
            answer.append(cnt)
            
            #배포 날짜 빼기(없어도 됨)
            map(lambda x: x-deploy, date)
            
            deploy = date.pop(0)
            cnt=1
    answer.append(cnt)
    
    return answer

 

 

deque()를 사용하면 빠를 듯 싶습니다. 

pop(0) -> O(n)

popleft() -> O(1)

 

하지만 길이가 짧아 비슷하긴합니다

from collections import deque
def solution(progresses, speeds):
    answer = []
    #몇 퍼센트 남았는지: 100-progresses
    percent = [100-i for i in progresses]
 
    #percent // speeds 나머지 있으면 +1
    date = []
    for i in range(len(percent)):
        d = percent[i]//speeds[i]
        date.append(d if percent[i] % speeds[i] == 0 else d+1)
    
    #새로운 배열에 날짜 담기 앞에 거 보다 날짜가 빠르면 같이 나감
    cnt = 1
    date = deque(date)
    deploy = date.popleft()
    while len(date) > 0:
        if deploy >= date[0]:
            cnt+=1
            date.popleft()
        else:
            answer.append(cnt)
            deploy = date.popleft()
            cnt=1
    answer.append(cnt)
    
    
    #다 없어질 때까지 +1
    return answer