문제 - 과제 진행하기

문제접근

1. 우선순위큐를 이용하여 주어진 과제들을 시작시간으로 오름차순으로 정렬
2. 멈춘 과제의 자료구조는 스택을 이용(최근 멈춘 과제부터 진행해야되기 때문에)
3. 현재 과제와 다음 해야될 과제를 비교
   1) 현재 과제를 끝내고 시간이 남은 경우 : 남는 시간동안 멈춘 과제 진행
   2) 현재 과제 끝나는 시간과 다음 해야될 과제의 시작 시간과 같은 경우 : 현재 과제 완료
   3) 남은 시간이 없는 경우 : 과제를 진행한 시간만큼 뺀 다음 스택에 저장
4. 남은 과제가 없으면 현재 과제와 멈춘 과제 모두 결과값에 저장

해당 문제는 복잡한 구현문제인 거 같다.

import java.util.*;

class Solution {
    public String[] solution(String[][] plans)
    {
        ArrayList<String> answer = new ArrayList<>();

        //과제들을 시간별로 오름차순
        PriorityQueue<subject> pq = new PriorityQueue<>(
                (x,y) -> (x.time - y.time));

        for(String []plan : plans)
        {
            String name = plan[0];
            String temp[] = plan[1].split(":");
            int time = Integer.parseInt(temp[0]) * 60 + Integer.parseInt(temp[1]);
            int left = Integer.parseInt(plan[2]);

            pq.offer(new subject(name,time,left));
        }

        //스택을 이용
        Stack<subject> wait = new Stack<>();

        while(!pq.isEmpty())
        {
            subject now = pq.poll();

            //현재시간
            int cntTime = now.time;
            int cntleft = now.left;

            //다음 과제들과 비교
            if(!pq.isEmpty())
            {
                subject nextSub = pq.peek();

                //현재 과제를 끝나고도 시간이 남는 경우
                if(cntTime + cntleft < nextSub.time)
                {
                    answer.add(now.name);
                    //현재시간 업데이트
                    cntTime += cntleft;

                    //남는 시간동안 멈춘 과제 진행
                    while(!wait.isEmpty())
                    {
                        subject rem = wait.pop();
                        //다음 과제 전까지 멈춘 과제를 끝내는 경우
                        if(cntTime + rem.left <= nextSub.time)
                        {
                            cntTime += rem.left;
                            answer.add(rem.name);
                        }else{//끝내지 못하는 경우
                            int time = rem.left - (nextSub.time - cntTime);
                            wait.push(new subject(rem.name,rem.time,time));
                            break;
                        }
                    }
                }else if(now.time + now.left == nextSub.time)//과제가 끝난뒤 바로 다음 과제를 하는 경우
                {
                    answer.add(now.name);
                }else //남는 시간이 없는 경우
                {
                    int leftTime = cntleft - (nextSub.time - now.time);
                    wait.push(new subject(now.name,now.time,leftTime));
                }
            }else{//남은 과제가 없다면
                
                answer.add(now.name);
                //멈춘 과제 모두 저장
                while(!wait.isEmpty())
                {
                    subject next = wait.pop();
                    answer.add(next.name);
                }
                
                
            }
        }

        String ans[] = new String[answer.size()];

        for(int i=0;i<answer.size();i++)
        {
            ans[i] = answer.get(i);
        }
        return ans;
    }

    class subject{
        String name;
        int time;
        int left;

        public subject(String name,int time,int left)
        {
            this.name = name;
            this.time = time;
            this.left = left;
        }

    }
}