프로그래머스 - 기능개발[java]

문제 풀이 방법

찾아야하는 값1: progresses + speeds * days >= 100 에 충족하는 days의 최소 값을 찾는다.

찾아야하는 값2: 배열의 index를 0은 첫째 날, 1은 둘째날, 2는 셋째날이라고 가정했을때 날마다 몇개의 기능이 배포될 수 있는지 배열에 담아서 return 한다.

중요설명

progresses 와 speeds 라는 이름의 매개 변수가 int[]의 형태로 주어진다.

progresses의 배열은 100 미만의 자연수를 포함한다
speeds는 100 이하의 자연수를 포함한다.

progresses는 기능 개발의 진도율을 의미한다.
speeds는 개발속도를 의미한다.

progresses + speeds * days가 100 이상일 경우 개발 완료 상태를 의미한다.

progresses가 모두 개발완료 되었을때(배열이 담은 모든 자연수가 100 이상이 되었을때), 각 기능(progresses의 자연수들)이 한번에 몇개 씩 배포가 될 수 있는지 days(각 기능들이 개발완료까지 소요된 일수)를 확인하여 답을 구한다.

1차 풀이 코드

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        int [] temp = new int[progresses.length];
        // 각 기능개발에 소요된 일수를 구해 temp에 담는다
        for(int i = 0; i < speeds.length; i++) {
            int remained = 100 - progresses[i];
            int days = remained / speeds[i];
            if(remained % speeds[i] != 0)
                days++;
            temp[i] = days;
        }
        
        // 하루에 몇개의 기능이 차례대로 배포될수 있는지 arraylist에 담는다
        for(int j = 0; j < temp.length; j++) {
            int earliestDay = temp[j];
            boolean canBeDeployed = true;
            int count = 1;
            if(temp[j] != 0) {
                for(int k = j + 1; k < temp.length && canBeDeployed; k++) {
                    if(temp[k] != 0) {
                        if(temp[k] <= earliestDay) {
                            count++;
                            temp[k] = 0;
                        } else
                            canBeDeployed = false;
                    }
                }
                al.add(count);
            }   
        }
        // 구한 답을 array 형태로 바꾸어 리턴한다.
        int[] answer = new int [al.size()];
        for(int n = 0; n < answer.length; n++)
            answer[n] = al.get(n);
        return answer;
    }
}

어떤 자료 구조를 써야하는지 모르고 처음 풀었을때의 코드이다. arraylist를 사용하여 loop이 두번 돌아서 시간복잡도가 O(N^2)으로 비효율적이나 모든 테스트케이스를 통과하였다.

큐를 활용한 풀이 코드

import java.util.*;
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> q = new LinkedList<Integer>();
        // 각 기능개발에 소요된 일수를 구해 queue에 담는다
        for(int i = 0; i < speeds.length; i++) {
            int remained = 100 - progresses[i];
            int days = remained / speeds[i];
            if(remained % speeds[i] != 0)
                days++;
            q.add(days);
        }
        
        // 하루에 몇개의 기능이 차례대로 배포될수 있는지 arraylist에 담는다
        int day = q.poll();
        int howManyFunc = 1;
        ArrayList<Integer> answer = new ArrayList<Integer>();
        while(!q.isEmpty()) {
            int nextDay = q.poll();
            if(day >= nextDay)
                howManyFunc++;
            else {
                day = nextDay;
                answer.add(howManyFunc);
                howManyFunc = 1;
            }
        }
        answer.add(howManyFunc);
        
        // 구한 답을 array 형태로 바꾸어 리턴한다.
        int[] ans = new int [answer.size()];
        for(int n = 0; n < ans.length; n++)
            ans[n] = answer.get(n);
        return ans;
    }
}

큐를 사용하여 nested loop이 제거되어 시간 복잡도 효율이 O(n)으로 향상 되었다.

새롭게 알게된 것

int[] ans = answer.toArray(new int [answer.size()]);

위와 같은 코드의 형태로 list를 array형태로 바로 변환하려 했으나 에러가 발생했다.

검색해보니 아래와 같은 이유로 int형 list는 형변환이 불가능하다고 한다.

primitive타입에 대한 Comparator가 없기 때문입니다.
자바에서는 이처럼 primitive 타입인지 아니면 객체인지에 따라 사용의 제약이 있는 경우가 있습니다. 그리고 int배열을 Integer배열이나 ArrayList로 손쉽게 바꿀 수 있는 방법은 없습니다. Lambda 쓰거나 for문 돌려야 합니다.