[프로그래머스] 알고리즘 고득점 kit - 기능개발 (Stack/Queue)

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586

 

 

<문제 설명>

•  하루에 한 번만 이루어지는 배포

•  작업의 개발 속도가 적힌 정수 배열 speeds

•  작업의 진도가 적힌 정수 배열 progressess

•  뒤에 있는 기능이 먼저 개발되더라도, 앞에 있는 기능이 배포될 때 같이 배포

•  각 배포마다 몇 개의 기능이 배포되는지 파악하는 것이 목표

 

<접근방법>

•  절대적으로 선입선출을 지키기 위한 Queue 생성

•  매일 배포되는 기능의 개수를 담을 ArrayList 생성

(배열에 바로 담을 수 없는 이유: 크기를 알지 못해서)

 

<풀이 로직>

•  Queue 에 담긴 작업이 100 달성시 poll

•  poll 한 데이터의 개수를 ArrayList 에 담기

•  ArrayList의 값들을 Array 로 옮기기

 

 

<코드 작성>

1단계

Queue 를 생성하고 제공받은 두 개의 배열을 활용하여

남은 일자를 계산 및 올림 처리하여 Queue 에 삽입한다

 

올림 처리하는 이유

progresses = [95], speeds = [4] 일 경우

 

올림 처리 없이 계산

((100 - 95) / 4 = 5) / 4 = 1.25

정수 나눗셈을 사용하면 결과는 '1'

이는 작업이 하루 만에 완료될 것으로 잘못 계산됨

 

올림 처리를 사용한 계산

((100 - 95 + 4 - 1) / 4 = 8) / 4 = 2

이 경우 결과는 정확하게 '2'

Queue 생성 및 각 기능의 완료 일수 계산 로직 구현 

Queue<Integer> deployQueue = new LinkedList<>();
int progressesLength = progresses.length;

for (int i = 0; i < progressesLength; i++) {
    int dueDate = (100 - progresses[i] + speeds[i] - 1) / speeds[i]; // 올림 처리
    deployQueue.offer(dueDate);
}

 

2단계

Queue 가 비어있기 전까지 head를 추출하고

head 와 그다음 head 와 작업 만료 날짜를 비교하여

같거나 날짜가 더 빠르다면 함께 추출하여 ArrayList 에 담기

head 추출 및 그 다음 head 비교하여 ArrayList 에 담기

ArrayList<Integer> deployCntPerDay = new ArrayList<>();
while (!deployQueue.isEmpty()) {
    int headDueDate = deployQueue.poll();
    int features = 1;
    while (!deployQueue.isEmpty() && deployQueue.peek() <= headDueDate) {
        deployQueue.poll();
        features++;
    }
    deployCntPerDay.add(features);
}

 

3단계

ArrayList 에 담긴 정답을

배열에 옮겨 담은 후 최종 답안 제출

ArrayList 에서 Array 로 옮기기

int[] answer = new int[deployCntPerDay.size()];
for (int i = 0; i < answer.length; i++) {
    answer[i] = deployCntPerDay.get(i);
}
return answer;

 

 

 

---

 

 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.ArrayList;

class Solution {
	public int[] solution(int[] progresses, int[] speeds) {
		Queue<Integer> deployQueue = new LinkedList<>();
		int progressesLength = progresses.length;
		
		for (int i = 0; i < progressesLength; i++) {
			int dueDate = (100 - progresses[i] + speeds[i] - 1) / speeds[i];
			deployQueue.offer(dueDate);
		}

		ArrayList<Integer> deployCntPerDay = new ArrayList<>();
		while (!deployQueue.isEmpty()) {
			int headDueDate = deployQueue.poll();
			int features = 1;

			while (!deployQueue.isEmpty() && deployQueue.peek() <= headDueDate) {
				deployQueue.poll();
				features++;
			}

			deployCntPerDay.add(features);
		}

		int[] answer = new int[deployCntPerDay.size()];
		for (int i = 0; i < answer.length; i++) {
			answer[i] = deployCntPerDay.get(i);
		}
		return answer; 
	}
}