[프로그래머스 / Java] 코딩테스트 연습: 기능개발 (스택 / 큐)

난이도: Level 2

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

프로그래머스

---

 

작업의 개수(progresses, speeds배열의 길이)는 100개 이하이다.

즉 데이터의 개수 N이 100밖에 안 되어서 시간 복잡도의 영향을 받지 않으므로 O(N^2)으로도 풀 수 있는 문제이다.

 

우선 큐와 리스트를 다음과 같이 선언한다.

counts는 배열의 임시 리스트이다.

배열은 크기를 조정시키기 어려우므로 우선 리스트로 선언하고 리턴할 때 배열로 바꿀 것이다.

 

    Queue<Work> queue = new LinkedList<>();     // 작업 큐

    List<Integer> counts = new ArrayList<>();   // 배포 1번 당 배포되는 기능의 수 리스트

 

 

큐의 타입인 Work 클래스는 다음과 같이 선언한다.

 

    class Work {

        int progress;   // 작업의 진도

        int speed;      // 작업의 속도

       

        Work(int progress, int speed) {

            this.progress = progress;

            this.speed = speed;

        }

    }

 

 

큐에 진도와 속도를 가지는 작업 객체를 생성해서 차례대로 모두 넣는다.

 

    // 진도와 속도를 가지는 작업을 생성해서 큐에 삽입

    for (int i = 0; i < progresses.length; i++) {

        queue.add(new Work(progresses[i], speeds[i]));

    }

 

 

다음은 기능개발을 시킬 주요 로직이다.

가장 밖에 있는 while문이 한 번 루프를 돌 때마다 배포를 1번 할 수 있다.

while문 안에 또 for문과 while문으로 큐 안의 데이터를 이중으로 탐색하는데, 데이터의 수가 100밖에 안되므로 이렇게 해도 된다.

while문 안에 있는 for문은 기능 개발을 하는 로직이고, while문 안에 있는 while문은 기능 배포를 하는 로직이다.

우선 while문 안의 for문으로 큐 안에 있는 모든 작업들의 진도를 해당 작업의 속도만큼 증가시킨다.

그리고 while문 안의 while문으로 큐 안을 또 탐색하는데, 큐가 빌 때까지 반복해도 되는 이유는 큐의 가장 상단에 있는 기능이 배포를 할 수 있는 조건에 맞지 않으면 그 전에 break로 탈출을 하기 때문이다.

큐의 가장 상단에 있는 기능이 배포를 할 수 있는 조건이라면 큐에서 꺼낸 후 이번에 배포할 수 있는 기능의 수 count를 1 증가시킨다.

배포할 기능이 있는지를 모두 탐색한 뒤 배포할 수 있는 기능의 수가 0이 아니라면, 즉 배포할 수 있는 기능이 존재한다면 위에서 선언한 counts 리스트에 배포할 수 있는 기능의 수 count를 추가한다.

위 과정이 배포 1번의 로직이다.

이것을 큐가 빌 때까지 반복한다. 

 

    // 작업 큐가 빌 때까지 반복

    // while문 루프 한번 당 배포 1번

    while (!queue.isEmpty()) {

        // 큐에 담긴 작업들을 모두 탐색

        for (Work work : queue) {

            // 해당 작업의 진도가 100 미만이라면

            if (work.progress < 100) {

                // 작업 진도에 작업 속도만큼 더하기

                work.progress += work.speed;    

            }

        }

       

        int count = 0;  // 배포 1번 당 배포되는 기능의 수

       

        // 작업 큐가 빌 때까지 반복

        while (!queue.isEmpty()) {

            // 큐의 맨 위에 있는 작업의 진도가 100 미만이라면

            if (queue.peek().progress < 100) {

                break;  // 배포 불가

            } else {    // 작업의 진도가 100 이상이라면

                queue.poll();   // 큐에서 작업 꺼내기 (배포 가능)

                count++;        // 배포 기능의 수 1 증가

            }

        }

   

        if (count != 0) {   // 배포되는 기능의 수가 0이 아니라면

            counts.add(count);  // 배포 1번 당 배포되는 기능의 수 리스트에 추가

        }

    }

 

 

마지막으로 counts 리스트의 크기만큼 배열 크기를 선언하고, 배열에 그대로 데이터를 옮겨 담아서 리턴해주면 된다.

 

    // 리스트를 배열로 변환

    int[] answer = new int[counts.size()];  

   

    for (int i = 0; i < counts.size(); i++) {

        answer[i] = counts.get(i);

    }

    return answer;  // 배포 1번 당 배포되는 기능의 수 배열 리턴

 

---

전체 코드

import java.util.*;
 
class Solution {
    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Work> queue = new LinkedList<>();     // 작업 큐
        List<Integer> counts = new ArrayList<>();   // 배포 1번 당 배포되는 기능의 수 리스트
        
        // 진도와 속도를 가지는 작업을 생성해서 큐에 삽입
        for (int i = 0; i < progresses.length; i++) {
            queue.add(new Work(progresses[i], speeds[i]));
        }
        
        // 작업 큐가 빌 때까지 반복
        // while문 루프 한번 당 배포 1번
        while (!queue.isEmpty()) {
            // 큐에 담긴 작업들을 모두 탐색
            for (Work work : queue) {
                // 해당 작업의 진도가 100 미만이라면
                if (work.progress < 100) {
                    // 작업 진도에 작업 속도만큼 더하기
                    work.progress += work.speed;    
                }
            }
            
            int count = 0;  // 배포 1번 당 배포되는 기능의 수
            
            // 작업 큐가 빌 때까지 반복
            while (!queue.isEmpty()) {
                // 큐의 맨 위에 있는 작업의 진도가 100 미만이라면
                if (queue.peek().progress < 100) {
                    break;  // 배포 불가
                } else {    // 작업의 진도가 100 이상이라면
                    queue.poll();   // 큐에서 작업 꺼내기 (배포 가능)
                    count++;        // 배포 기능의 수 1 증가
                }
            }
        
            if (count != 0) {   // 배포되는 기능의 수가 0이 아니라면
                counts.add(count);  // 배포 1번 당 배포되는 기능의 수 리스트에 추가
            }
        }
        
        // 리스트를 배열로 변환
        int[] answer = new int[counts.size()];  
        
        for (int i = 0; i < counts.size(); i++) {
            answer[i] = counts.get(i);
        }
 
        return answer;  // 배포 1번 당 배포되는 기능의 수 배열 리턴
    }
}
 
class Work {
    int progress;   // 작업의 진도
    int speed;      // 작업의 속도
    
    Work(int progress, int speed) {
        this.progress = progress;
        this.speed = speed;
    }
}