[알고리즘]STEP1-1주차 스택/큐(기능개발)

👼🏻복습링크

기능개발

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

1️⃣ 첫번째 풀이

❗ deque 이용

from collections import deque

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

1. progresses, speeds를 deque로 변환
2. while 문
   • progresses의 원소가 있는 동안 반복
   • count를 0으로 선언. count는 한번에 배포될 수 있는 기능의 개수를 의미
   • for문을 통해 얻어진 count가 0이 아니면 answer.append(count)
3. 첫 번째 for 문
   • progresses[i]+=speeds[i]를 하여 하루동안 개발된 진도를 계산
4. 두 번째 for 문 (진도가 100 이상인 기능을 제거)
   • progresses의 길이만큼 반복
   • progresses[0]이 100이상이면 count+=1을 progresses와 speeds에서 모두 popleft()한다.

2️⃣ 두번째 풀이

❗ 다른 사람의 풀이를 보고 참고한 풀이. 반복문을 하나만 사용하여 시간복잡도를 줄일 수 있음

from collections import deque

def solution(progresses, speeds):
    answer = []
    cnt=0
    day=0
    progresses=deque(progresses)
    speeds=deque(speeds)
    
    while progresses:
        if progresses[0]+speeds[0]*day>=100:
            progresses.popleft()
            speeds.popleft()
            cnt+=1
        else:
            if cnt>0:
                answer.append(cnt)
                cnt=0
            day+=1
    answer.append(cnt)
        
            
    return answer

1. cnt =0 선언. cnt는 한번에 배포할 수 있는 기능의 수를 의미
2. day=0 선언. day는 개발하는 일수를 의미
3. progresses, speeds를 deque로 변환
4. while 문
   • progresses의 원소가 있는 동안 반복
   • progresses의 첫 번째 원소가 day 이후의 개발 진도가 100이상이면 progresses와 speeds에서 popleft(진도가 100미만인 기능을 발견할 때까지 반복)
   • cnt+=1을 하여 배포 가능한 기능 수 더하기
   • progresses의 첫 번째 원소의 진도가 100이하이면 cnt개수 판별하여 0초과일 경우 answer.append(cnt) 후 0으로 초기화
   • day+=1로 일자 수 늘리기
5. while문 마친 후 마치막 cnt 값 answer.append(cnt)