문제 링크

링크

문제 설명

제한 사항

입출력 예 및 설명은 링크 참조~

풀이

1. 일단 시작시간을 기준으로 plans 배열을 정렬하자.
2. 현재 진행중인 과제 및 미뤄놓은 과제를 스택에 담자.
   2-1 stack.peek() > 현재 진행중인 과제
   2-2 그 밑에 있는 데이터들 > 미뤄놓은 과제들
3. 현재 진행중인 과제의 start + playtime이 방금 받은 과제의 start보다 크거나 작거나로 분기한다.
   3-1 전자 (현재 진행중인 과제를 미뤄야할 경우)에는 진행중이었던 과제를 스택에다 넣되, play한 만큼 playtime을 갱신해야함
   3-2 후자 (현재 진행중인 과제를 완료할 수 있는 경우)에는 완료했다고 배열에다가 넣고, 대신 여기서 중요하다. 3-3으로
   3-3 현재 진행중인 과제를 완료했으면 다음 과제를 시작하기까지 자투리 시간이 있다.
   이 자투리 시간동안 스택에서 peek()한 과제를 play해야한다.
4. 여튼 3-3 로직을 잘 구현하면 끝난다.

간만에 머리 기름칠 제대로 했당.. 반례 찾느라 혼났다 ㅋㅋ

코드

import java.util.*;
class Task {
    int index;
    int start;
    int playtime;
    public Task(int index, int start, int playtime) {
        this.index = index;
        this.start = start;
        this.playtime = playtime;
    }
}
class Solution {
    public int getTime(String time) {
        return Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5));
    }
    public String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        Arrays.sort(plans, new Comparator<String[]>(){
            @Override
            public int compare(String[] o1, String[] o2) {
                return o1[1].compareTo(o2[1]);
            }
        });
        Stack<Task> ing = new Stack();
        ArrayList<String> end = new ArrayList<>();        
        for(int i = 0; i < plans.length; i++) {
            int start = getTime(plans[i][1]);
            int playtime = Integer.parseInt(plans[i][2]);
            if(ing.isEmpty()) {
                ing.push(new Task(i, start, playtime));
                continue;
            }
            Task now = ing.pop();
            if(now.start + now.playtime > start) { //하던거 스택에 넣고 지금꺼 푸시
                ing.push(new Task(now.index, start, now.playtime - (start - now.start))); //하던거 다시 넣고
            } else {
                end.add(plans[now.index][0]);
                //남는 시간에 ing 스택에 있는것들 해주기
                int remain = start - (now.start + now.playtime);
                while(remain > 0 && !ing.isEmpty()) {
                    int del = ing.peek().playtime - remain;
                    ing.peek().playtime = Math.max(0, del);
                    
                    if(del <= 0)
                    {
                        remain = -1 * del;
                        end.add(plans[ing.pop().index][0]);
                    }else {
                        remain = 0;
                    }
                }
            }
            ing.push(new Task(i, start, playtime)); //새로운거 푸시            
        }
        int k;
        for(k = 0; k < end.size(); k++)
            answer[k] = end.get(k);
        while(!ing.isEmpty())
        {
            answer[k++] = plans[ing.pop().index][0];
        }
        return answer;
    }
}