[프로그래머스] 과제 진행하기 / 자바(Java)

문제

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

프로그래머스

 

유사한 문제

2023.10.30 - [[IT] 코딩테스트/[문제 및 풀이] 프로그래머스] - [프로그래머스] 택배상자 / 자바(Java)

---

해설

시작 시간 순서대로 정렬 후 조건에 맞춰 진행하며 구현하면 해결 가능한 문제입니다.

0. 입력값 정리

        for(int i=0;i<plans.length;i++){
            m.put(i,plans[i][0]);
            newPlans[i][0] =  i;
            String[] start = plans[i][1].split(":");
            newPlans[i][1] =  Integer.parseInt(start[0])*60+Integer.parseInt(start[1]);
            newPlans[i][2] =  Integer.parseInt(plans[i][2]);
        }
        
        Arrays.sort(newPlans, (o1,o2)->o1[1]-o2[1]);

객체를 따로 만들지 않고 int배열로 입력값을 정리하기 위해 String값을 저장하기 위한 Map을 생성해 각 String값의 정보를 index로 저장합니다.

시와 분의 단위 요소를 제거하기위해 분으로 합쳐 저장해 줍니다.

이후 입력 시간을 기준으로 정렬하여 앞에서 부터 차례대로 찾을 수 있도록 해줍니다.

 

 

1. 과제 미루기 판단

            curTime = newPlans[i][1]+newPlans[i][2];
            if(i<plans.length-1){
                nextTime = newPlans[i+1][1];
                if(curTime>nextTime){
                    s.push(new int[]{newPlans[i][0], curTime-nextTime});
                    curTime = nextTime;
                    continue;
                }
            }

지금 수행할 과제의 시작 시간과 수행 시간을 더해 최종 시간(curTime)으로, 다음 과제의 시작 시간(nextTime)을 구해줍니다. 이때 i를 배열의 범위에 넣기위해 최종값을 제외해 주어도, 규칙상에 마지막 과제는 항상 스택에 들어가지 않고 바로 실행되므로 무관합니다.

다음 과제의 시작시간 전에 지금 수행하는 과제가 끝나지 않는다면,  남는 시간만큼을 스택에 넣어줍니다.

 

 

2. 과제 진행

answer[idx++] = m.get(newPlans[i][0]);

과제가 미뤄지지 않았다면 이번 과제의 String값을 검색해 answer에 넣어줍니다. answer의 인덱스값은 i와는 다르므로 따로 더해줍니다.

 

 

3. 미뤄진 과제 진행

            while(!s.isEmpty()){
                int ableTime = nextTime-curTime;
                int[] task = s.pop();
                // 멈춘 과제 진행
                if(ableTime >= task[1]){
                    answer[idx++] = m.get(task[0]);
                    curTime += task[1];
                }else{// 과제를 멈추고 다음 작업 진행
                    s.push(new int[]{task[0],task[1]-ableTime});
                    break;
                }
            }

다음 과제의 시작시간에서 지금의 과제가 수행완료된 시간을 빼면 다음과제까지의 남은 시간(ableTime)이 남습니다.

이때 틈틈히 스택에 있던 과제들을 빼내어 작업합니다. 남은 시간이 수행할 작업 시간보다 많이 남았다면 answer에 추가 후 수행 시간을 추가하여 남은시간(ableTime)이 줄도록 정해줍니다.

만약 부족하다면 과제를 다시 멈춘 후 스택에 넣습니다.

 

1, 2, 3을 반복해서 수행해 줍니다.

 

4. 남은 과제 진행

        while(!s.isEmpty()){
            answer[idx++]=m.get(s.pop()[0]);
        }

최종적으로 스택에 남은 과제들은 시간에 상관없이 최근 넣은 과제들 순으로 수행하므로 pop을 통해 순서대로 answer에 넣어주어 문제를 해결합니다.

 

주의점

• 과제를 끝낸 시점에 새로운 과제와 멈췄던 과제가 있는 경우 새로운 과제를 진행해야 한다 -> 멈췄던 과제를 진행시 다음 진행 시간을 알아야 한다.

---

코드

import java.util.*;
class Solution {
    public String[] solution(String[][] plans) {
        String[] answer = new String[plans.length];
        Stack<int[]> s = new Stack<>();
        Map<Integer, String> m = new HashMap<>();
        int[][] newPlans = new int[plans.length][3];

        for(int i=0;i<plans.length;i++){
            m.put(i,plans[i][0]);
            newPlans[i][0] =  i;
            String[] start = plans[i][1].split(":");
            newPlans[i][1] =  Integer.parseInt(start[0])*60+Integer.parseInt(start[1]);
            newPlans[i][2] =  Integer.parseInt(plans[i][2]);
        }
        
        Arrays.sort(newPlans, (o1,o2)->o1[1]-o2[1]);
        
        int idx=0;
        int curTime = 0;
        int nextTime = 0;
        for(int i=0;i<plans.length;i++){
            //1. 과제 미루기 판단
            curTime = newPlans[i][1]+newPlans[i][2];
            if(i<plans.length-1){
                nextTime = newPlans[i+1][1];
                if(curTime>nextTime){
                    s.push(new int[]{newPlans[i][0], curTime-nextTime});
                    curTime = nextTime;
                    continue;
                }
            } 
            
            //2. 과제 진행
            answer[idx++] = m.get(newPlans[i][0]);
            //3. 미뤄진 과제 진행
            while(!s.isEmpty()){
                int ableTime = nextTime-curTime;
                int[] task = s.pop();
                // 멈춘 과제 진행
                if(ableTime >= task[1]){
                    answer[idx++] = m.get(task[0]);
                    curTime += task[1];
                }else{// 과제를 멈추고 다음 작업 진행
                    s.push(new int[]{task[0],task[1]-ableTime});
                    break;
                }
            }
            

        }
        // 과제 탐색 후 스택에 남은 과제들 진행
        while(!s.isEmpty()){
            answer[idx++]=m.get(s.pop()[0]);
        }
        return answer;
    }
}