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

🔅문제🔅

 

progresses는 순서대로 작업이 되어야 해서

첫번째 작업 93프로 완료, 남은 7프로를 1 속도를 통해 한다면 7일 소요,

두번째 작업 30프로 완료, 남은 70프로를 30속도로 하면 3일 소요,

세번재 작업도 같은 방식으로 9일 소요된다. 

 

[7, 3, 9] 두번째 작업이 먼저 끝났더라도 첫번째 작업이 완료되지 않아 배포를 기다리는 상황

7일째에 첫번째, 두번째 작업 배포 -> 2

9일째에 세번째 작업 배포 -> 1

 

최종 출력 : [2, 1]

 

 

 

👾해결과정👾

 

먼저 소요 기간을 리스트로 받아보고자 아래처럼 작성하였다. 99로 한 이유는 딱맞는 기간까지 +1로 올림하고자 함

*올림 : ceil()

for i in range(0, len(speeds)):
        answer.append((99 - progresses[i]) //speeds[i] +1)

 

그리고 두 개의 반복문을 통해서 

첫번째 반복문(i)에서는 count =1 로 항상 초기화하고

두번째 반복문(j)에서는 j를 1씩 올려가며 i값과 비교하면서 i보다 j가 같거나 작으면 count를 +1 해준다.

그리고 i값은 j 위치로 이동시킨다.

 

def solution(progresses, speeds):
    answer = []
    arr = []
    for i in range(0, len(speeds)):
        answer.append((99 - progresses[i]) //speeds[i] +1)
    i = 0
    while i < len(answer):
        count = 1
        j = i + 1
        while j < len(answer) and answer[i] >= answer[j]:
            count += 1
            j += 1
        arr.append(count)
        i = j
    return arr

 

이렇게 해서 해결하였는데 사실 이 문제는 스택/큐 문제이기 때문에 의도한 바와 다르게 문제를 푼 것이다. 

(시간복잡도도 높게 나옴)

 

 

같은 로직으로 큐를 이용해서 풀어보자

from collections import deque

def solution(progresses, speeds):
	answer =[]
    days = deque()
    
    for i in range(len(progresses)):
    	days.append((100 - progresses[i] + speeds[i] - 1) // speeds[i])
    
    while days:
    	count = 1
        first = days.popleft() #첫번째 소요기간
        
        while days and first >= days[0]:# 같은 배포일에 함께 배포
        	count += 1
            days.popleft()
        
        answer.append(count)
	return answer