[PS] 프로그래머스 - 과제 진행하기 ( 구현, 자료구조 ) with JAVA

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

프로그래머스

 

 

◎ 문제풀이 

 

문제의 요구사항을 요약하면 다음과 같다. 

 

1) 우선순위는 새로 시작한 과제가 높다. 
2) 기존 진행중이던 과제는 우선순위가 낮다. 
3) 멈추어둔 과제가 여러개이면 최근에 멈춘 순으로 시작

4) 과제를 끝낸순서로 이름을 배열에 담아 return  

 

요구사항을 다음과 같은 알고리즘으로 구현하면 된다. 

1) 우선순위큐를 사용하여  과제를 시간을 기준으로 오름차순 정렬한다.  
2) 첫 시간부터 1분씩 반복증가하며 체크한다.
3) 중간에 멈춘 과제는 최근에 멈춘 순으로 과제를 수행하므로 STACK에 넣어둔다. 
4) 다음 과제 시간이 되면 진행중이던 과제는 Stack에 넣고 과제를 수행한다. 
5) 과제를 끝냈을 때, 새로운 과제에 시간이 안되었으면 Stack에서 과제를 꺼낸다.
6 우선순위큐의 모든 과제를 끝내고, Stack도 모두 비어지면 프로그램을 종료한다. 

 

 

◎ 코드

import java.util.*;

class Solution {
    
    public class Subject{
        public String name;
        public int time;
        public int processTime;
        
        public Subject(String name, String time, String processTime){
            this.name = name;
            this.time = changeToMinute(time);
            this.processTime = Integer.parseInt(processTime);
        }
        
        public int changeToMinute(String time){
            String[] timeArr = time.split(":");
            int hour = Integer.parseInt(timeArr[0]);
            int min = Integer.parseInt(timeArr[1]);

            return hour*60 + min;
        }
    }
    public String[] solution(String[][] plans) {
        
        PriorityQueue<Subject> subjects = new PriorityQueue<>((s1,s2)-> s1.time - s2.time);
        Stack<Subject> waitingSubjects = new Stack<>();
        List<String> completedSubjects = new ArrayList<>();
        
        for(int i=0;i<plans.length;i++){
            subjects.add(new Subject(plans[i][0],plans[i][1],plans[i][2]));
        }
        
        Subject currSubject = subjects.poll();
        int currTime = currSubject.time;
        boolean flag = true;
        while(flag){
            
            int minTime = 0;
            boolean isProcessing = true;
            
            while(true){
                
                // 처리가 완료되는 경우
                if( minTime == currSubject.processTime ){
                    completedSubjects.add(currSubject.name);
                    isProcessing = false;
                    
                    // 신규 과제가 있는 경우
                    if( !subjects.isEmpty() && currTime == subjects.peek().time){
                        currSubject = subjects.poll();
                        currTime += minTime;
                        break;
                    }
                    
                    // 대기하고 있는 과제가 있는 경우
                    else if(!waitingSubjects.isEmpty()){
                        currSubject = waitingSubjects.pop();
                        currTime += minTime;
                        break;
                    }
                    
                    // 대기 과제도 없고 신규과제도 없는 경우 
                    else if(waitingSubjects.isEmpty()&&subjects.isEmpty()){
                        flag = false;
                        break;
                    }
                    
                 }
                
                // 새로운 과제가 들어오는 경우 
                if( !subjects.isEmpty() && (currTime + minTime) == subjects.peek().time ){
                    if(isProcessing){
                        currSubject.processTime -= minTime;
                        waitingSubjects.push(currSubject);    
                    }
                    currSubject = subjects.poll();
                    currTime += minTime;
                    break;
                }
                
                // 과제 처리 중...
                minTime++;
            }        
        }
        
        return completedSubjects.toArray(new String[completedSubjects.size()]);
        
        
    }
    
}