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

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

 

코딩테스트 연습 - 기능개발

[문제 설명]

 

위 문제를 해결하는 방법은 두 가지가 있습니다.

 

첫 번째 - 큐

두 번째 - 배열

 

저는 문제를 빠르게 해결하기 위해 그냥 배열로 풀었습니다. (이게 편하거든요)

 

[완전 탐색]

import java.util.*;

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int complete[] = new int [progresses.length];
        boolean check[] = new boolean[progresses.length];
        ArrayList<Integer> answer = new ArrayList<>();

        for(int i=0; i<progresses.length; i++){
            int nonClear = (100 - progresses[i]);
            complete[i] =  (nonClear % speeds[i] == 0) ? nonClear / speeds[i] : nonClear / speeds[i] + 1;
        }

        for(int i=0; i<complete.length; i++){
            if(!check[i]) {
                int count = 1;
                check[i] = true;

                for (int j = i + 1; j < complete.length; j++) {
                    if (complete[i] >= complete[j] && !check[j] && check[j-1]) {
                        count++;
                        check[j] = true;
                    }
                }

                answer.add(count);
            }
        }

        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
}

 

[해결 방법 - 큐]

1. 각 작업의 배포일을 계산해서 배열에 넣는다.

 

2. 배포 순위가 높은 작업의 배포일을 큐에 넣는다.

 

3. 반복문의 인덱스를 i=1부터 시작해서 배포일의 배열 길이만큼 반복한다.

    1. 큐의 맨 앞의 값과 배포일[i]과 비교하여 큐의 맨 앞 값이 크거나 같다면 큐에 배포일[i]를 넣어준다.

    2. 큐의 맨 앞 값이 작으면 큐의 크기를 answer 배열에 넣어주고 큐를 전부 제거한 후 큐에 배포일[i]를 넣어준다. 

 

4. 큐가 남아 있다면 큐의 사이즈를 answer 배열에 넣어준다.

 

5. answer 리턴