[스택/큐] 프로그래머스 Lv1. 기능 개발 - Python

🗂️ 문제

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

프로그래머스

 

💡 접근법

progresses 리스트 자체를 큐로 사용한다.

 

이때 while 문을 통해 진도(progress)에 작업 속도(speed)를 계속해서 더해간다.

만약 첫 번째 요소의 진도율이 100% 이상일 경우, 이는 배포가 가능한 작업이 된다. 따라서 첫 번째 요소 이후에도 배포가 가능한 작업이 있는지 카운팅하고, 해당 요소들은 큐에서 삭제한다.

 

이때 큐에서 삭제하는 작업의 효율성을 위해 deque()를 사용한다.

💡 deque()를 사용하는 이유
파이썬의 리스트는 동적 배열로 구성되어 있어 맨 앞(인덱스 0) 원소를 제거한 뒤, 뒤에 있는 모든 원소를 앞으로 한 칸씩 옮겨야 하므로 O(N)이라는 비효율이 발생한다. 반면, deque는 연결리스트와 비슷한 방식으로 내부적으로 양쪽 끝에 대한 접근을 빠르게 처리할 수 있도록 구현되어 있기 때문에 O(1)을 보장할 수 있다.

 

 

😎 내 코드

from collections import deque

def solution(progresses, speeds):
    answer = []
    
    progress_queue = deque(progresses)
    speed_queue = deque(speeds)
    
    while(progress_queue):
        for i in range(len(progress_queue)):
            progress_queue[i] += speed_queue[i]
        
        release_cnt = 0
        for p in progress_queue:
		        if p >= 100:
				        release_cnt += 1  
		        else:
				        break
        
        if release_cnt >= 1:
            answer.append(release_cnt)
            for i in range(release_cnt):
                progress_queue.popleft()
                speed_queue.popleft()

    return answer

 

👀 배운 코드

from math import ceil

def solution(progresses, speeds):
    answer = []
    
    # 각 작업이 완료되기까지 걸리는 일 수 계산
    days = [ceil((100 - p) / s) for p, s in zip(progresses, speeds)]
    
    # 첫 번째 작업의 기준 완료일
    base_day = days[0]
    count = 0  # 배포할 작업 수
    
    for day in days:
        if day <= base_day:
            # 기준 완료일보다 작거나 같으면 같은 배포에 포함
            count += 1
        else:
            # 새로운 배포 시작
            answer.append(count)
            count = 1
            base_day = day
    
    # 마지막 남은 작업 배포
    answer.append(count)
    
    return answer

배포 가능한 작업의 수를 한 번만 계산하도록 하고, 불필요한 반복을 없애기 위해 각 작업이 완료되기까지 필요한 “일 수”를 미리 계산한 뒤, 완료일을 앞에서부터 순회하며, 배포 가능한 작업 수를 한 번만 계산한다.

 

이 방식은 progresses와 speeds를 한 번 순회하면서 필요한 연산을 처리하므로, 시간복잡도는 O(N)이다.

 

🧐 배운 점

• 현재 코드는 O(N^2)라는 시간복잡도를 갖는데, 문제에서 입력값의 크기가 매우 크다면(수천수만 이상) 분명 다소 비효율적이겠지만, 입력값의 크기가 100 이하이므로 크게 문제가 되지는 않는다. 하지만 그래도 더 효율적으로 풀 필요가 있어 보인다 ..ㅎ