[알고리즘-자바] 프로그래머스 스택/큐 > 기능개발, 테스트 11번 틀리는 이유

본 글은 다크모드에 최적화되어 있습니다.

 

문제

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

프로그래머스

언어

자바 Java

로직

테스트 1~11 중에 11번만 자꾸 틀려서 결국 코드를 찾아봤습니다. 그 이유를 찾았는데, 개발이 완료되는 날짜를 구하는 코드에 문제가 있었습니다. 차근차근 알아봅시다.

 

큐 선언

큐의 경우 FIFO 구조를 갖습니다. 즉 큐에 값을 저장한 순서대로 꺼낼 수 있습니다. 여기서 인덱스를 저장하는 이유는 작업 진도와 걸리는 시간을 둘 다 사용해야 하기 때문입니다.

Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < progresses.length; i++)
    que.offer(i);

★개발에 걸리는 시간 구하기

테스트 11번이 틀리는 이유가 개발에 걸리는 시간을 잘못 구했기 때문입니다. 

 

진행 정도가 담긴 배열 [96, 94], 진행 속도가 담긴 배열 [3,3]이 있다고 합시다. 개발을 완료하는 데 걸리는 시간은 얼마일까요? 둘 다 이틀이 걸립니다. 그러나 기존 코드를 보면 정수형으로 값을 다루고 있기 때문에 (100 - 96) / 3을 하면 1을 반환하게 됩니다. 

 

따라서 정수형이 아닌 실수형으로 값을 다루어 소수점이 존재하게 된다면 올림처리를 해주어야 합니다. 

자바에서는 Math.ceil() 메서드를 제공하는데, 소수점이 존재하는 실수값을 올림처리 해줍니다. (100 - 96) / 3은 1.3333333... 을 반환하므로 Math.ceil을 사용하면 2.0을 반환하게 되고, 이를 int타입으로 형변환을 해주면 2를 반환하게 됩니다.

기존 코드

private int getReleaseTime(int progress, int speed) {
    return (100 - progress) / speed;
}

수정한 코드

private int getReleaseTime(int progress, int speed) {
    return (int) Math.ceil((double) (100 - progress) / speed);
}

배포 개수 구하기

이전 배포에 걸린 시간과 현재 배포에 걸린 시간을 비교하여야 합니다. 여러 개의 작업을 한 번에 배포하기 위해서는 이전 작업 배포 시간 > 현재 작업 배포시간을 만족해야 합니다. 

아래 조건문은 그 반대이기 때문에, 현재 작업을 이전 작업과 동시에 배포할 수 없는 작업임을 의미합니다. 

int count = 0;
int prevReleaseTime = 0;
while (!que.isEmpty()) {
    int poll = que.poll();
    int nowReleaseTime = getReleaseTime(progresses[poll], speeds[poll]);

    if (nowReleaseTime > prevReleaseTime) {
        if (prevReleaseTime != 0) {
            result.add(count);
            count = 0;
        }
        prevReleaseTime = nowReleaseTime;
    }
    count++;
}

 

여기서 이전 작업 시간이 0인지 확인하는 조건문이 존재하는데요. 그 이유는 초기값을 0으로 설정하였기 때문입니다.

첫 번째 작업을 개발 완료하는 데 걸리는 시간 > 이전 작업 시간(초기값=0) -> 반드시 이 조건을 만족해 버리게 됩니다. 따라서 이경우에는 바로 배포하는 것이 아닌 다음 작업과 비교를 하여 동시에 배포를 할지 아니면 단독으로 배포를 할지 판단해야 합니다.

if (prevReleaseTime != 0) {
    result.add(count);
    count = 0;
}

---

코드

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

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

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

        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < progresses.length; i++)
            que.offer(i);

        int count = 0;
        int prevReleaseTime = 0;
        while (!que.isEmpty()) {
            int poll = que.poll();
            int nowReleaseTime = getReleaseTime(progresses[poll], speeds[poll]);

            if (nowReleaseTime > prevReleaseTime) {
                if (prevReleaseTime != 0) {
                    result.add(count);
                    count = 0;
                }
                prevReleaseTime = nowReleaseTime;
            }
            count++;
        }

        result.add(count);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    private int getReleaseTime(int progress, int speed) {
        return (100 - progress) / speed;
    }
}