[프로그래머스 Lv.2] 기능개발

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

프로그래머스

 

 

✅ 정답풀이

import math
from collections import deque

def solution(progresses, speeds):
    answer = []
    progress_days=[math.ceil((100-x)/speeds[idx]) for idx,x in enumerate(progresses)]

    queue=deque(progress_days)

    done=queue[0]
    count=0

    while queue:
        if queue[0]<=done: 
            queue.popleft()
            count+=1 
        else:
            answer.append(count)
            count = 0
            done=queue[0]
    answer.append(count)


    return answer

가장 심플한 방법으로 풀이한것 같다.

우선순위 큐로, 맨앞의 요소가 빠져나가기 전까지 뒤에 기다리고있는 작업은 빠져나갈수 없다.

 

일단, 남은 작업 일수를 리스트로 만들어주고, 이를 큐로 만들어준다.

그리고 가장 첫번째 요소를 확인하면서, 첫번째요소의 작업일 이하에 대해서만 큐가 함께 빠져나갈 수 있고, 카운트를 해준다. 

빠져나가는 작업일보다 크면, 아직 작업이 남았기 때문에 빠져나갈 수 없고, 그때 큐가 빠져나가는것을 막기 때문에, 그때를 기점으로 answer에 답을 넣어주고, 다시 카운트를 하기위해 count와 맨앞의 큐를 초기화 해주었다. 

 

중단시점에, answer에 카운트를 넣어주는 방식으로 코드를 작성하다보니

마지막 작업이 끝났을땐 answer에 넣어줄수없어, while문이 종료되면 넣어주는식으로 작성했다.

 

 

✅ JavaScript 풀이

function solution(progresses, speeds) {
    var answer = [];
  
    //1. 작업일 배열 생성
    const work=progresses.map((v,i)=>Math.ceil((100-v)/speeds[i]));
    //2. 순회

    let deploy=work[0];
    let count=0;
    
    for(let i=0;i<work.length;i++){
        
        if(work[i]>deploy){
            answer.push(count);
            count=0;
            deploy=work[i];
        }
        count++;
    }
    answer.push(count); //마지막 요소 push
    return answer;

}

 

 

 

 

풀면 좋을 다른 우선순위 큐 문제

 

https://www.acmicpc.net/problem/1966

 

백준 1966번 : 프린터큐

# 인쇄=맨앞요소 제거시, 
# list(stack)는 pop(0)=O(n)
# Queue는 popleft()=O(1)  -> Queue 사용

# 첫번째 요소가 queue에서 max값이여야 출력이 가능

import sys
from collections import deque
input=sys.stdin.readline
n=int(input())
find=False


for _ in range(n):
    q=deque() #queue 생성 

    n,target=map(int,input().split())
    priority=list(map(int,input().split()))
    
    for idx,p in enumerate(priority):
        q.append((idx,p)) #(index:우선순위)
    
    result=0
    
    while True:
        # 첫번째 요소가 현재 큐에서 가장 큰 우선순위인지 확인
        max_priority=max(q,key=lambda x:x[1])[1]
        first=q.popleft()
  

        if first[1]==max_priority:
            result+=1
            #target 확인
            if target==first[0]:
              print(result)
              break
        else:
            #뒤로가기
            q.append(first)