[프로그래머스] 기능개발 - python

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

프로그래머스

문제 정보

문제 유형 : stack/queue

설계 방법

소요 시간을 미리 계산해두고 q에 저장 (q는 deque)

q.popleft해서 앞에 있는 기능이 배포될 때 함께 배포될 수 있는 뒷 기능 저장

코드

실패 코드

from collections import deque
def solution(progresses, speeds):
    answer = []
    cnt = 1
    q = deque()
    for i in range(len(progresses)):
        if (100-progresses[i]) % speeds[i] == 0:
            q.append((100-progresses[i]) // speeds[i])
        else:
            q.append((100-progresses[i]) // speeds[i] + 1)
    while q:
        v = q.popleft()
        if len(q) > 0:
            if v >= q[0]:
                cnt += 1
            else:
                answer.append(cnt)
                cnt = 1
        else:
            answer.append(cnt)
    return answer

테스트 2,3,4,5,6,7,9,10에서 실패 발생 왜지 ?

 

아 반례 찾았음

🗯️ 반례) progresses : [40, 93, 30, 55, 60, 65], speeds : [60, 1, 30, 5 , 10, 7], return : [1,2,3]

 

이 경우 q = [1,7,3,9,4,5]

내가 짠 코드대로하면 result = [1,2,2,1] 나옴

[9,4,5] 여기서 4가 5보다 작으니까 cnt = 1로 초기화 해버림

 

코드 수정

from collections import deque
def solution(progresses, speeds):
    answer = []
    cnt = 1
    q = deque()
    for i in range(len(progresses)):
        if (100-progresses[i]) % speeds[i] == 0:
            q.append((100-progresses[i]) // speeds[i])
        else:
            q.append((100-progresses[i]) // speeds[i] + 1)
    while q:
        v = q.popleft()
        lst = list(q)
        for i in lst:
            if v >= i:
                q.popleft()
                cnt += 1
            else:
                break
        answer.append(cnt)
        cnt = 1
    return answer

 

다른 풀이

import math

def solution(progresses, speeds):
    progresses = [math.ceil((100 - a) / b) for a, b in zip(progresses, speeds)]
    answer = []
    front = 0, 0

    for idx in range(len(progresses)):
        if progresses[idx] > progresses[front]:  
            answer.append(idx - front)
            front = idx 
    answer.append(len(progresses) - front)  

    return answer