[프로그래머스/Level2] 과제 진행하기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 스택/큐

필요 자료구조
- Plan 객체
- 잠시 멈춘 과제 저장용 스택(또는 큐)
- 완료된 과목 저장용 정답 리스트

 

1. Plan 객체를 생성해 배열에 넣고, 배열을 시작 시간 순 오름차순으로 정렬한다.

2. 0부터 마지막-1 인덱스까지 Plan 객체 배열을 순회한다.

• 현재 계획 (pp[i])과 다음 계획(pp[i+1])을 비교한다.
• 만약 현재 계획의 종료 시간이 다음 계획의 시작 시간 이후인 경우, 과제를 잠시 멈춘다.
  • 현재 계획을 남은 시간으로 저장한다. (남은 시간 = 현재 계획의 종료 시간 - 다음 계획의 시작 시간)
  • 잠시 멈춘 과제 저장용 스택에 현재 계획을 push한다.
• 과제를 멈추지 않아도 되는 경우
  • 정답 리스트에 현재 계획의 이름을 넣는다.
  • 여유시간 restTime(= 다음 계획의 시작 시간 - 현재 계획의 종료 시간)을 구한다.
  • 여유시간이 있는 동안 && 스택이 비기 전까지 아래 과정을 반복한다.
    • 스택의 맨 위에 있는 가장 최근 정지된 계획의 실행 시간과 여유 시간의 값을 빼서 비교한다. (timeDiff)
    • timeDiff 값을 정지된 계획의 실행 시간의 값으로 갱신한다. (stopPlan.playTime = timeDiff)
    • timeDiff의 값이 0보다 작거나 같다면 종료된 것이므로, 정답 리스트에 해당 과목의 이름을 추가한다.

 

3. Plan 객체 배열의 마지막 인덱스는 따로 정답 리스트에 넣고, 스택에 남은 계획들도 정답 리스트에 마저 넣는다.

4.리스트를 배열로 변환해 출력한다.

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {    
    public String[] solution(String[][] plans) {
        Plan[] pp = new Plan[plans.length];
        for(int i = 0 ; i < plans.length ; i++) {
            pp[i] = new Plan(plans[i]);
        }        
        Arrays.sort(pp, (a, b) -> a.start - b.start); // 시작 시간 순 오름차순 정렬
        
        Stack<Plan> stop = new Stack<>(); // 멈춘 과제들
        List<String> list = new ArrayList<>();
        
        for(int i = 0 ; i < pp.length -1 ; i++) {
            Plan now = pp[i];
            Plan next = pp[i+1];
                        
            // [과제 중지] 현재 계획의 종료 시간이 다음 계획의 시작 시간 이후인 경우
            if(now.getEndTime() > next.start) {
                now.playTime = now.getEndTime() - next.start;
                stop.push(now);
                continue;
            }
            
            // [과제 완료]
            list.add(now.name); // 현재 계획 이름 넣기
            
            int restTime = next.start - now.getEndTime();   // 여유 시간
            
            // 다음 계획 시작 시간까지 여유가 있는 동안 && 스택이 비기 전까지
            while(restTime > 0 && !stop.isEmpty()) {
                Plan stopPlan = stop.peek();
                
                int timeDiff = stopPlan.playTime - restTime;    // 여유 시간과 비교
                stopPlan.playTime = timeDiff;
                restTime = timeDiff * -1;
                
                if(timeDiff > 0)    break;
                
                list.add(stop.pop().name);                
            }
        }
        
        // 마지막 인덱스 넣기
        list.add(pp[pp.length -1].name);
        
        // 스택에 남은 계획들 정답에 넣기
        while(!stop.isEmpty())
            list.add(stop.pop().name);       
        
        // 리스트 -> 배열
        return list.toArray(new String[list.size()]);
    }
}
 
class Plan {
    String name;
    int start;
    int playTime;
    
    public Plan(String name, String start, String playTime) {
        this.name = name;
        String[] t = start.split(":");
        this.start = Integer.parseInt(t[0]) *60 + Integer.parseInt(t[1]);
        this.playTime = Integer.parseInt(playTime);
    }
    
    public Plan(String[] plan) {
        this(plan[0], plan[1], plan[2]);
    }
    
    public int getEndTime() {
        return start + playTime;
    }
}

 

 

 

 

 

 

➕ 다른 풀이 방식

- 개인적으로 이게 더 깔끔하고 추구미 풀이인 듯✅

[pro] 프로그래머스 level2 176962 과제 진행하기 (Java) - 그리디

 

- 재귀 함수 이용한 풀이

[코테]프로그래머스 - 과제 진행하기

---

💦 어려웠던 점

- 문제 이해를 오래 함

- 구현의 문제

 

 

🧐 새로 알게 된 내용

- (시간*60 + 분) 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Level2] 과제 진행하기 (JAVA)