프로그래머스 lv2. 기능개발 (스택/큐로 풀기)

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

프로그래머스

스택과 큐를 공부하고 프로그래머스의 스택/큐 카테고리에 있는 Lv2 문제에 적용시켜보았습니다. 

기능 구현의 속도와 진행 상태를 받아서, 배포할 때 몇개의 기능이 동시에 배포될 수 있을지 계산하는 문제인데요.

현실에서 사용할 법한 문제라서 재미있게 풀었습니다

• 스택: LIFO (싱크대에 쌓여있는 접시를 생각하면, 마지막에 쌓인 접시가 먼저 세척됨)
  • append() : 맨 뒤에 붙임
  • pop(): 맨 뒤에 값 뺌
• 큐: FIFO (음식점 줄서기 생각하면 먼저 온 사람이 먼저 들어감)
  • append(): 맨 뒤에 붙임
  • leftpop(): 맨 앞에 값 뺌 

두 단계로 나누어 풀었습니다.

1. 작업 별 배포까지 걸리는 작업 일 수 구하기

2. 배포 때 같이 배포되는 작업의 갯수 구하기 

 

1. 작업 별 배포까지 걸리는 작업 일 수 

작업이 완료되는 100 에서 현재까지 작업이 진행된 숫자를 빼주면 남은 작업량이 남습니다. 

남은 작업량을 작업속도로 나누어주면, 앞으로 몇일이 걸리는지 알 수 있는데

만약 딱 떨어지지 않을 경우 다음날 배포로 넘어가기 때문에 반올림 처리를 해주었습니다. 

 

남은 작업 일 수 = math.ceil(100-progresses)/speeds 

 

예시)

progresses = [93,30,55]

speeds = [1,30,5]

-> 남은 작업 일 수 = [7, 3, 9]

 

2. 배포 때 같이 배포되는 작업의 갯수 

첫번째 작업을 먼저 배포에 대기 시키고, 다음 작업이 같이 배포가 가능한 지 확인합니다.

만약 이미 작업이 끝나 (첫번째 작업의 작업일수보다 적거나 같음) 대기중이라면 대기에 추가해주고, 아직 작업중인 작업(배포 예정인 작업보다 남은 작업일 수가 큰 ) 이 나올 때까지 반복합니다. 

 

위에 예시로 보면

남은 작업 일 수 = [7,3,9]

1) 

첫번째 작업은 7일이 걸립니다.

배포 대기 = [7]

남은 작업에서 제외 빼줌 = [3,9] (큐의 leftpop() 사용)

 

2) 

7일 뒤 다음 작업이 완료되었는지 봅니다.

3일이면 완료되는 작업이라 이미 끝나서 이번 배포에 같이 들어갈 수 있으니 배포 대기에 추가합니다.

배포 대기 = [7,3]

남은 작업에서 빼줌 = [9] (큐의 leftpop() 사용)

 

3) 

다음 작업도 같이 배포 가능한지 살펴봅니다.

다음 작업은 9일이 소요되므로 아직 2일이 더 남아 같이 배포될 수 없습니다. 

따라서 이번 배포에는 배포 대기에 있는 2개만 배포되고 배포 대기 스택을 비워줍니다. 

return 2

배포 대기 = [] 

 

4)

2일 뒤 완료된 작업이 배포 대기에 추가 됩니다. 

배포 대기 = [9]

남아있는 작업이 없으므로 작업을 배포하고 끝냅니다. 

return 1

 

<코드>

import math,  collections
def solution(progresses, speeds):
    time = collections.deque()
    for p,s in zip(progresses,speeds):
        time.append(math.ceil((100-p)/s))
        
    print(time)
    result = []
    r = []

    while time:
				# result 리스트 비워져 있을때 무조건 time 큐의 0번째 인덱스 값 추가해주기
        if not result:
            result.append(time[0])
            time.popleft()
        # result 리스트 채워져있고, 0번째 인덱스(앞에 태스크)의 남은 일자수가 뒤에 일자보다 큰 경우 
				# 배포될때 뒤에 태스크도 함께 되어야 하니까, result에 추가해줌 
        elif result and result[0]  >=  time[0]:
            result.append(time[0])
            time.popleft()
            
				# 첫번째 태스크보다 큰 값이 나오면, 이제 배포할 태스크 갯수 끝! 
				# r에 있는 인자의 갯수를 리턴한 다음에 result 리스트는 비워준다. 
        elif result and result[0]  < time[0]:
            r.append(len(result))
            result = []
            
		# 마지막엔 배포할 태스크보다 오래걸리는게 없으므로 result 에 남아있는 모든 태스크 갯수를 마지막에 붙여준다.  
    r.append(len(result))
    return r