프로그래머스_스택/큐_기능 개발 (JAVA)

문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.   제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자연수입니다. 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다. 입출력 예   입출력 예 설명 첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다. 두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다. 세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다. 따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

 

 

굳이 스택이나 큐구조를 사용해야 하는가 의문이 드는 문제입니다. 문제를 아주 직관적으로 풀면 큐를 사용하게 되긴 한데 그게 맞는지는 잘 모르겠습니다. 일단 어떻게 풀건 문제 자체는 간단한 문제입니다.

 

 

---

 

 

일단 제가 푼 방식은 한 번의 순회만 사용했습니다. 각 작업을 끝내는데 걸리는 일자는 쉽게 계산이 가능하고, 앞의 작업이 끝나야 뒤의 작업을 배포할 수 있으므로 앞의 숫자보다 작은 일수를 가진 값은 한번에 배포되는 세트라고 볼 수 있습니다. 예를 들어 작업 완료까지 걸리는 일자가 { 5일,3일,4일,9일,6일 } 이라면 5일보다 작은 3,4일까지 한세트이고 9,6일이 한세트가 되는 것이죠.

 

최대값을 찾는 알고리즘처럼 max값을 두고 순회하다가 max값보다 큰 값이 나오면 다시 다른 세트로 인식해서 처리하면 쉽게 풀 수 있을 것 같습니다. 

 

import java.util.LinkedList;

class Solution {

	public int[] solution(int[] progresses, int[] speeds) {

		double[] days = new double[progresses.length];

		double max = 0;
		LinkedList<int[]> result = new LinkedList<>();
		for (int i = 0; i < progresses.length; i++) {

			// 끝낼 수 있는 일자
			days[i] = Math.ceil((100 - progresses[i]) / speeds[i]);

			// max보다 큰 값이 나올 경우 새로운 세트로 시작
			if (days[i] > max) {
				max = days[i];
				result.add(new int[] { 1 });

			// max보다 작은 값일 경우 max값이 시작된 count와 한 세트
			} else {
				result.getLast()[0]++;
			}
		}

		// 일반 배열로 복사 후 리턴
		int size = result.size();
		int[] answer = new int[size];
		for (int i = 0; i < size; i++) {
			answer[i] = result.pollFirst()[0];
		}

		return answer;
	}
}

 

 

 

---

 

 

 

직관적인 구조로 큐를 이용해 짜본 코드입니다. 일단 모든 작업 정보를 큐에 넣어둔 뒤 반복문이 한 번 돌 때마다 진행률을 올려주고, 가장 앞의 작업이 진행률 100퍼센트 이상이 되는 순간 진행률 100프로 이상인 작업을 한번에 큐에서 빼주는 방식입니다. 아래 코드보다 반복문 횟수를 많이 줄일 수 있긴 하지만 그렇다고 해도 쓸데없이 반복문이 너무 많이 돌아가기 때문에 좋지 않을 듯합니다. 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution {

    public int[] solution(int[] progresses, int[] speeds) {

        List<int[]> queue = new LinkedList<>();
        for (int i = 0; i < progresses.length; i++) {
            queue.add(new int[] { progresses[i], speeds[i] });
        }

        List<Integer> result = new ArrayList<>();
        while (queue.size() > 0) {

            for (int[] arr : queue) {
                arr[0] += arr[1];
            }

            if (queue.get(0)[0] >= 100) {

                int count = 0;
                for (int i = 0; i < queue.size();) {

                    if (queue.get(i)[0] >= 100) {
                        queue.remove(i);
                        count++;
                    } else {
                        break;
                    }
                }
                result.add(count);
            }
        }

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

        return answer;
    }
}