프로그래머스(JAVA) - STACK/QUEUE (기능개발)

 

문제정리

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses
각 작업의 개발 속도가 적힌 정수 배열 speeds
배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정

 

처음 작성한 코드

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        int a = 1;

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < progresses.length; i++) {
            int num = 100 - progresses[i];

            int count = num / speeds[i];

            list.add(count);
        }

        int count = 0;

        List<Integer> list2 = new ArrayList<>();

        for (int i = 1; i < list.size(); i++) {

            if (list.get(count) >= list.get(i)) {
                a++;
                continue;
            } else {
                count = i;
                list2.add(a);
                a = 1;
            }
        }
        list2.add(a);
        return list2.stream().mapToInt(i -> i).toArray();
    }
}

 

list에는 각각 기능 작업이 몇 일간 작업 후 배포가 가능한지 들어가게 하였고, 그 아래 list를 비교하여 기간보다 작거나 같을 경우를 카운트하여 다시 list2에 넣을 수 있도록 하였는데 결과는... 실패

 

 

뭐가 문제일까..
.
.

int count = num / speeds[i]; 와 이거 할 때 왜 올림된다고 생각한거지..?
Math.ceil을 사용해서 올림 처리해야지...!

수정 코드

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

class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        List<Integer> days = new ArrayList<>();
        
        // 각 작업이 완료되기까지 걸리는 날짜 계산
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int day = (int) Math.ceil((double) remain / speeds[i]);
            days.add(day);
        }

        List<Integer> result = new ArrayList<>();
        int maxDay = days.get(0); // 첫 번째 작업이 기준
        int count = 1;

        for (int i = 1; i < days.size(); i++) {
            if (days.get(i) <= maxDay) {
                count++; // 같은 배포일에 포함
            } else {
                result.add(count);
                maxDay = days.get(i); // 새로운 기준 업데이트
                count = 1;
            }
        }

        result.add(count); // 마지막 배포 그룹 추가
        return result.stream().mapToInt(i -> i).toArray();
    }
}

 

변수명도 좀 더 알아보기 쉽게 변경, 반올림 처리했고, 인덱스를 비교하여 값을 냈는데 해당 날 자체를 비교할 수 있도록 변경하였다.

 

시간은..

---

큐로 해결하는 방법

import java.util.*;

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

        // 1. 각 기능이 완료되기까지 걸리는 날짜를 큐에 저장
        for (int i = 0; i < progresses.length; i++) {
            int remain = 100 - progresses[i];
            int day = (remain % speeds[i] == 0) ? (remain / speeds[i]) : (remain / speeds[i] + 1);
            q.add(day);
        }

        // 2. 배포 그룹 계산
        int x = q.poll();
        int count = 1;
        while (!q.isEmpty()) {
            if (x >= q.peek()) {
                count++;
                q.poll();
            } else {
                list.add(count);
                count = 1;
                x = q.poll();
            }
        }
        list.add(count);

        // 3. 결과 배열로 변환
        return list.stream().mapToInt(i -> i).toArray();
    }
}

 

일단 큐 사용은 아직 어색한데...
큐는 FIFO로 먼저 들어온 것이 먼저 나가는 자료구조

add()와 offer() 동일하게 데이터를 추가하는 방법을 말한다.
(add()는 큐가 꽉 차 있으면 예외 발생하고, offer()은 false를 반환)

peek()는 큐에서 맨 앞에 있는 데이터를 확인 큐가 비어있으면 null을 반환

poll()은 큐에서 맨 앞에 있는 데이터를 꺼내면서 동시에 삭제! 비어있으면 null을 반환
remove()도 poll()과 동일하게 맨 앞 데이터를 꺼내면서 삭제! 하지만 큐가 비어 있으면 예외 발생