오늘의 학습내용
- 자료구조 큐
- 다른 방법으로 생각하기
공부한 내용
문제를 읽고 'progress에는 먼저 배포되어야 하는게 먼저 들어오기 때문에 FIFO' 이므로 큐의 자료구조라는 점을 바로 인지할 수 있었다. 그러나 주어진 조건은 큐에 들어온 모든 progress들이 시간이 지날수록 각 speed에 맞춰 커지기 때문에 큐로만 단순구현하는게 어렵다고 판단했다. 따라서 큐에 progress값을 넣는게 아닌 index값을 넣음으로써 구현을 완료했다.
오늘의 회고
- x일이 지날때마다 모든 큐에는 speeds[i]*x 만큼
- 큐.peek 가 100이 되면 나머지 100이된것들 모두 poll -> cnt ++; cnt 를 리스트로
- 큐.isEmpty()가 될때까지
문제
프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.
또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.
먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.
내 풀이
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds){
//먼저 들어온 자료가 특정 조건을 만족하면 나가므로 큐
int[] answer = {};
Queue<Integer> queue = new LinkedList<>();
for(int i=0; i<progresses.length; i++){
queue.add(i);
}
List<Integer> result = new ArrayList<>();
//큐에서 계속 빼내기
//만료기간에 대해 정의할때
//이전의 큐에 해당하는 day값들이랑 비교해서 더 크면, -> 이전까지 쌓이던 큐에 있던 변수반환
int count = 0;
int days = 0;
while(!queue.isEmpty()){
//예) 처음부터 나오는 수
int index = queue.poll();
//한 기능이 만료되는 일정
int expiration = (int)Math.ceil((double)(100-progresses[index]) / speeds[index]);
//만료기간이 더 긴 다음의 index가 있는 경우
if(expiration > days){
//더 큰 기간이 걸린게 있으면 그동안의 count값 반환
if(days!=0){
result.add(count);
count = 0;
}
days = expiration;
}
count++;
}
result.add(count);
answer = result.stream().mapToInt(Integer::intValue).toArray();
return answer;
}
}다른 사람 풀이
import java.lang.System;
import java.lang.Math;
import java.util.ArrayList;
class Solution {
int progressesCount;
int[] needDays;
ArrayList<Integer> workCountStorage;
public int[] solution(int[] progresses, int[] speeds) {
//Init
progressesCount = progresses.length;
needDays = new int[progressesCount];
workCountStorage = new ArrayList<>();
//필요한 작업일 계산
this.calcNeedDays(progresses, speeds);
//this.viewAll(needDays, 0);
//동시에 진행된 프로세스 계산
for(int step=0; step<progressesCount;)
{
int stepNeedDay = needDays[step];
//날짜 동시에 경과
for(int remainStep=step; remainStep<progressesCount; remainStep++)
{
needDays[remainStep] -= stepNeedDay;
}
//this.viewAll(needDays, step);
//완료한 작업까지의 갯수
int workCount = 1;
for(;step+workCount<progressesCount; workCount++)
{
if(needDays[step+workCount] > 0)
{
break;
}
}
System.out.println("workCount:"+workCount);
//완료한 작업 갯수 저장
workCountStorage.add(workCount);
//작업 갯수만큼 step 증가
step += workCount;
}
//int[] answer = {};
int[] answer = Solution.convertIntegers(workCountStorage);
return answer;
}
private void calcNeedDays(int[] progresses, int[] speeds)
{
for(int i=0; i<progressesCount; i++)
{
double remainProgress = 100 - progresses[i];
double fNeedDay = remainProgress / speeds[i];
needDays[i] = (int)Math.ceil(fNeedDay);
}
}
public static int[] convertIntegers(ArrayList<Integer> integers)
{
int size = integers.size();
int[] ret = new int[size];
for (int i=0; i<size; i++)
{
ret[i] = integers.get(i).intValue();
}
return ret;
}
private void viewAll(int[] array, int startIdx)
{
System.out.print("viewAll:");
int arrayCount = array.length;
for(int i=startIdx; i<arrayCount; i++)
{
System.out.print(array[i]+",");
}
System.out.println();
}
}