[Greedy] 과제진행하기(실패분석 - 문제 부족하게 이해)

접근

과제 진행하기

이 문제는
1. Greedy를 통한 시작시간 정렬
2. Stack을 이용한 구현

위와 같이 두 가지 과정을 거쳤습니다.

현재 과제와 새로운 과제 사이에 시간이 붕뜨게 되면
중단된 과제를 Stack에서 꺼내 남은 시간만큼 진행하게 됩니다.

그러나 중단된 과제를 하나만 꺼내 진행하고 끝내버렸습니다.
문제의 의도는 중단된 과제를 하나만 꺼내 진행하고 그래도 시간이 남는다면
다음 중단된 과제를 꺼내서 진행해야 하고 이게 남은 시간이 0이 될 때까지 반복됩니다.

따라서 stopfind 메서드를 내부 메서드로 선언하여 시간이 남는 경우 Stack에서 중단된 과제를 계속 꺼내눈 재귀함수를 구현하였습니다.

전체적인 흐름은 아래와 같습니다.
1. 시작시간이 빠른 순서대로 정렬한다.
2. plans를 앞에서부터 하나씩 꺼내고
3. 과제를 하는 중간에 새로운 과제 시작시간에 도달하면
4. 하던 과제를 중단하고 중단된 과제를 Stack에 넣는다.
5. 만약에 현재 과제와 새로운 과제 사이에 시간이 붕 뜬다면
6. Stack에 중단된 과제를 꺼내 진행한다. 단, 그래도 시간이 남는다면
7. Stack에 중단된 과제를 계속 꺼낸다. 남는 시간이 0이 될때까지
8. 0이 되면 새로운 과제를 시작한다.

나의 풀이

import java.util.*;

class Solution {
    
    static Stack<String[]> st;
    static   ArrayList<String> answer;
    
    public ArrayList<String> solution(String[][] plans) {
        answer = new ArrayList<>();
        // 시작하기로 한 시각이 되면 시작
        // 새로운 과제를 시작할 시각이 되었을 때 +  기존 과제 진행 중 -> 진행 중인 과제 멈추고 새로운 과제
        // 진행중이던 과제 끝 -> 멈춘 과제 이어서 진행 
        // 단 진행중이던 과제 끝, 멈춘 과제 < 새롭게 시작하는 과제
        // 멈춘 과제 여러개 -> 가장 최근에 멈춘 과제부터 시작
        
        // 과제 plans 3~1000 [name, start, playtime]
        // name : 소문자, 중복된 원소 없음
        // start : 과제의 시작 hh:mm 형태 모든 과제의 시작 시작은 다르다 00 ~23
        // playtime : 과제 마치는데 걸리는 시간 , 단위는 분 1~100 0은 없다
        
        // 진행중이던 과제가 끝나는 시각 = 새로운 과제를 시작해야하는 시각이 같은 경우 -> 진행중이던 과제는 끝
        
        //1. 시간 순으로 정렬
        
        Comparator<String []> comp = new Comparator<>(){
            
           public int compare(String[] c1, String[] c2){
               return c1[1].compareTo(c2[1]);
           }
        };
        
        
        Arrays.sort(plans,comp);
        
        //2. stack을 이용해서 중단된 과제 담기
        st = new Stack<>();
        
        // 3. 과제를 돌며 검사하기
        int i=0;
        while(i<plans.length-1){
            // 현재
            String[] preArr = plans[i][1].split(":");
            int pretime = Integer.parseInt(preArr[0]) * 60 + Integer.parseInt(preArr[1]);
            
            // playtime 
            int playtime = Integer.parseInt(plans[i][2]);
           
            // 새로운 
            String[] newArr = plans[i+1][1].split(":");
            int newtime = Integer.parseInt(newArr[0]) * 60 + Integer.parseInt(newArr[1]);
            
            
            
            // 중간에 새로운 과제가 존재하는 경우 
            if(pretime+playtime>newtime){
                String[] stop =  new String[3];
                stop[0] = plans[i][0];
                stop[1] = Integer.toString(pretime+playtime-newtime);
                st.add(stop);
            // 작거나 같은 경우    
            }else{
               
                 answer.add(plans[i][0]);
              
                if(pretime+playtime<newtime){
                   // 멈춘 과제가 있는 경우
                   if(st.size()>0){
                      String[] STpop = st.pop();
                      // remainTime = 다음 새로운 과제까지의 붕뜬 시간 
                      int remainTime=Integer.parseInt(STpop[1])-(newtime-(pretime+playtime));
                       System.out.println(STpop[0]+":"+remainTime);
                       // 같은 경우 정답으로
                      if(remainTime == 0){
                           answer.add(STpop[0]);
                       // 남은 시간이 있는 경우 다음 과제에 전달하기   
                       }else if(remainTime<0){
                          answer.add(STpop[0]);
                          // 다음 과제에 전달하는 메서드
                          stopfind(-1*remainTime);
                       // 붕뜬 시간이 중단된 과제 처리시간보다 작은 경우
                       }else{
                           STpop[1] = Integer.toString(remainTime);
                           // 남은 처리시간 다시 Stack에 넣기
                           st.add(STpop);
                       }
                   }
               }
            }
            i++;
        }
        
        answer.add(plans[plans.length-1][0]);
        int size = st.size();
        if(size>0){
            for(int j=0;j<size;j++){
                String[] remain = st.pop();
                answer.add(remain[0]);
            }
        }
        
      
        // 과제를 끝낸 순서대로 이름을 배열에 담아 return
        return answer;
    }
    // 남은 시간을 다음 과제에 전달하는 메서드
    static void stopfind(int remainTime){
        if(st.size()>0){
          String[] STpop = st.pop();   
          int nextRemain = Integer.parseInt(STpop[1])- remainTime;
          if(nextRemain>0){
               STpop[1] = Integer.toString(nextRemain);
               st.add(STpop);
          }else if(nextRemain==0){    
               answer.add(STpop[0]);
          }else{
              answer.add(STpop[0]);
              stopfind(-1*nextRemain);
          }   
        }
    }
    
}