[1주차 - Queue & Heap] 기능개발

본 포스팅은 프로그래머스에서 진행하는 코딩테스트와 실무역량 모두 잡는 알고리즘 스터디(Python반) 6기에 참여 하면서 공부한 내용을 정리한 것이다. (https://programmers.co.kr/learn/courses/12441)

 

1. [문제설명] 
2. [문제풀이] 
3. [코드리뷰를 통해 발견한 개선할 점] 
4. [리뷰완료 후 전체코드] 

 

---

[문제설명]

기능개발

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100% 일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발 속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

 

제한 사항

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

progressesspeedsreturn

[93,30,55]

[1,30,5]

[2,1]

입출력 예 설명

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다. 

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

 

---

[문제풀이]

작업 목록의 첫번째 요소 부터 배포 가능한 작업이 연속적으로 몇개가 있는지 확인하고 그 수만 큼 작업 목록과 진척도 목록을 제거한다.

제거된 작업목록 수량만큼을 결과 리스트에 추가해준다.

작업 목록에 진척도를 적용한다.

만약 확인할 작업 리스트가 없는 경우 결과 리스트를 반환한다.

def solution(progresses, speedes):
    answer = []
    while progresses:
        counter = 0
        # 배포 가능한 작업 수를 확인
        for i in range(len(progresses)):
            if progresses[i] >= 100:
                counter += 1
            else:
                break
        for i in range(counter):
            progresses.pop(0)
            speedes.pop(0)
        if counter > 0:
            answer.append(counter)
        for i in range(len(progresses)):
            progresses[i] += speedes[i]
    return answer

 

---

[코드리뷰를 통해 발견한 개선할 점]

 

1. python에서 queue 자료구조를 사용해야 할 경우는 deque 라이브러리를 사용하도록 한다.

완료된 작업과 진척도를 제거할 때 list의 가장 앞 요소를 pop 하도록 했는데, 이는 선형 시간만큼의 시간 복잡도를 보인다는 것을 알게 되었다. deque를 사용하면 popleft()를 통해 동일한 작업을 상수 시간에 할 수 있다. 위의 코드에 deque를 적용한 코드는 다음과 같다.

from collections import deque


def solution(progresses, speeds):
    answer = []
    queue_progresses = deque(progresses)
    queue_speeds = deque(speeds)
    while queue_progresses:
        counter = 0
        for i in range(len(queue_progresses)):
            if queue_progresses[i] >= 100:
                counter += 1
            else:
                break
        for i in range(counter):
            queue_progresses.popleft()
            queue_speeds.popleft()
        if counter > 0:
            answer.append(counter)
        for i in range(len(queue_progresses)):
            queue_progresses[i] += queue_speeds[i]
    return answer

 

2. 각 기능 진도를 100이상으로 하기위해 며칠이 소요되는지를 계산한 결과를 토대로 배포 수량을 확인하면 시간 복잡도를 O(n)으로 개선할 수 있다.

import math


def solution(progresses, speeds):
    answer = []
    spent_days = list()
	
    # 완료까지 남은 작업일을 ceil함수를 사용하여 구할 수 있다.
    # 남은 작업량을 작업속도로 나눈 결과가 5.xxx 라고 한다면 5일 full로 소요되고
    # .xxx만큼 하는데도 하루가 소요 되므로 올림하여 총 6일이 소요된다고 보면 된다.
    for i in range(len(progresses)):
        spent_days.append(math.ceil((100 - progresses[i]) / speeds[i]))

    # 첫번 째 작업에 대한 남은 작업일을 저장한다.
    max_val = spent_days[0]
    # 동시에 종료할 수 있는 작업 수를 카운팅한다.
    # max_val 이하의 작업일 수에 해당하는 작업들을 모두 카운팅 할 것이다.
    count = 0
    for i in range(len(spent_days)):
        c_val = spent_days[i]
		# 현재 선택한 작업의 남은 작업일 수가 동시에 끝낼 수 있는 최대 작업일 수 이하라면 카운팅한다.
		if max_val >= c_val:
            count += 1
        # 현재 선택한 작업의 남은 작업일 수가 기존의 동시에 끝낼 수 있는 최대 작업일을 초과한다면
        # 1. 지금까지 카운팅한 결과를 저장하고
        # 2. 동시에 끝낼 수 있는 최대 작업일을 현재 작업의 남은 작업일로 변경한 뒤 
        # 3. 카운터를 1로 초기화 한다.
        else:
            answer.append(count)
            max_val = c_val
            count = 1
    answer.append(count)

    return answer