[알고리즘 고득점 kit/스택, 큐] 기능개발

첫번째 기능이 먼저 배포되어야 그다음 두번째, 세번째 기능이 배포될 수 있으니 이건 큐 문제로 풀어야 한다.   

 

그냥 덱 모듈을 쓰도록 하자. from collections import deque

# 덱 선언
dq = deque([])

# 덱에 원소 삽입
dq.append()

# 덱의 첫번째 원소 제거
dq.popleft()
# 덱의 마지막 원소 제거
dq.popright()

물론 큐 문제니까 큐 모듈을 쓸 수도 있다. import queue

하지만 큐니까 원소를 deque하게 되면 시간복잡도가 O(N)이 된다. (맨 앞의 원소를 빼면 두번째 원소부터 끝까지를 다 한칸씩 앞으로 당겨줘야한다.)

 

-> 차라리 큐랑 스택 문제는 다 덱으로 푸는게 장땡!

from collections import deque

pro_q = deque([])

def solution(progresses, speeds):
    answer = []
    # 덱 자료구조로 만들어서 저장
    pro_q = deque(progresses)
    spd_q = deque(speeds)
    
    # 한 반복마다 pro_q에 spd_q값 더해주면서 맨 앞에서부터 100 이상인 값들 추려내기
    while(1):
        pnum = len(pro_q)
        if not pnum:
            break
        
        for i in range(pnum):
            pro_q[i] += spd_q[i]
        
        ans = 0
        # 앞에서부터 보되 100안넘으면 종료하고 다음 반복으로
        for i in range(pnum):
            if pro_q[i] >= 100:
                ans +=1
            else:
                break
            
        if ans != 0:
            answer.append(ans)
            
        for _ in range(ans):
            pro_q.popleft()
            spd_q.popleft()
    return answer

한 반복마다 프로그레스에 스피드를 더해주고, 첫번째 원소부터 100이상이라는 조건 만족하는지 보고, 다음 반복으로 넘어가서 또 스피드를 더해주고, 반복