알고리즘 스터디 2주차

알고리즘 스터디 2주차 과제로 기능개발 문제 풀이를 진행하였다.

코딩테스트 연습 - 기능개발 | 프로그래머스 스쿨 (programmers.co.kr)

리팩토링 전 문제 풀이 코드

• 먼저 progresses 배열로 받은 각 작업의 남은 작업 시간을 계산하여 remainedDays 배열에 추가하였다.
• 각 배포마다 몇 개의 기능이 배포되는지를 return할 answerList 배열을 선언
• remainedDays배열에서 선 작업의 남은 작업시간과 후 작업의 남은 작업 시간을 비교
  • 후 작업의 남은 작업 시간이 선 작업보다 작을 경우 후 작업도 선 작업된 기능과 함께 배포될 것이므로 count는 1 증가
  • 후 작업의 남은 작업 시간이 선 작업보다 클 경우 다음 날 배포 될 것이므로 기존 count 값을 answerList에 추가하고, 해당 작업이 선 작업이 되어 다시 비교가 진행 됨
  • 비교할 후 작업이 없어지면 기존 count값이 answerList에 추가되어 answerList가 최종 반환됨

import java.util.*;

class Solution {
    public ArrayList<Integer> solution(int[] progresses, int[] speeds) {

        //각 작업의 남은 작업 시간을 계산하여 remainedDays 배열에 추가
        int [] remainedDays = new int [progresses.length];
        for (int i =0; i<progresses.length; i++){
            if((100-progresses[i])%speeds[i] != 0){
                remainedDays[i] = (100-progresses[i])/speeds[i] + 1;
            }else{
                remainedDays[i] = (100-progresses[i])/speeds[i];
            }
        }
       //remainedDays배열에서 선 작업의 남은 작업시간과 후 작업의 남은 작업 시간을 비교
       ArrayList<Integer> answerList = new ArrayList<>();
        int front = 0;
        int count = 1;
        for(int i=0; i<remainedDays.length; i++){
            if((i+1)==remainedDays.length){
                answerList.add(count);
                break;
            }
            if(remainedDays[i+1]<=remainedDays[front]){
                count++;
            }else{
                front = i+1;
                answerList.add(count);
                count=1; 
            }
        }

        
        return answerList;
    }
}

리팩토링 후 코드

다른 사람의 문제풀이를 참고하여 큐를 이용해 효율적으로 코드를 짤 수 있음을 알게 되었다.

• 배포되지 않은 작업을 보관할 큐 선언
• 각 작업의 남은 작업 날짜 계산
  • double 타입으로 나누기
  • Math.ceil : 소수 값이 존재할 때 값을 올리는 역할을 하는 함수
• 큐가 비어있지 않고, 해당 작업의 남은 날짜가 가장 최근에 보관된 작업의 남은 작업 날짜보다 크면, 큐의 사이즈를 anwerList에 추가하고 큐를 초기화함
• 해당 작업의 남은 날짜가 가장 최근에 보관된 작업의 남은 날짜보다 작으면, 큐에 추가 됨

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<>();
        List<Integer> answerList = new ArrayList<>();

				 //각 작업의 남은 작업 시간을 계산
        for (int i = 0; i < speeds.length; i++) {
            double remain = (100 - progresses[i]) / (double) speeds[i];
            int date = (int) Math.ceil(remain);

            if (!q.isEmpty() && q.peek() < date) {
                answerList.add(q.size());
                q.clear();
            }
						//큐에 데이터 삽입 
            q.offer(date);
        }

        answerList.add(q.size());

        int[] answer = new int[answerList.size()];

        for (int i = 0; i < answer.length; i++) {
            answer[i] = answerList.get(i);
        }

        return answer;
    }
}