[programmers] 과제 진행하기

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

프로그래머스

 

---

< 과제 진행하기 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	static class Plan {
		private String name;
		private int start;
		private int playtime;

		public Plan(String name, int start, int playtime) {
			this.name = name;
			this.start = start;
			this.playtime = playtime;
		}
	}

	public String[] solution(String[][] plans) {
		String[] answer = new String[plans.length];

		PriorityQueue<Plan> queue = new PriorityQueue<>(new Comparator<Plan>() {
			@Override
			public int compare(Plan o1, Plan o2) {
				return o1.start - o2.start;
			}
		});

		for (int i = 0; i < plans.length; i++) {
			int start = Integer.parseInt(plans[i][1].split(":")[0]) * 60 + Integer.parseInt(plans[i][1].split(":")[1]);
			queue.add(new Plan(plans[i][0], start, Integer.parseInt(plans[i][2])));
		}

		Stack<Plan> stack = new Stack<>();
		int idx = 0, now = 0;

		while (!queue.isEmpty()) {
			if (stack.isEmpty()) {
				stack.add(queue.poll());
				now = stack.peek().start;
			} else if (now + stack.peek().playtime > queue.peek().start) {
				stack.peek().playtime -= (queue.peek().start - now);
				stack.add(queue.poll());
				now = stack.peek().start;
			} else {
				now += stack.peek().playtime;
				answer[idx++] = stack.pop().name;
			}
		}

		while (!stack.isEmpty()) {
			answer[idx++] = stack.pop().name;
		}

		return answer;
	}
}

 

과제 이름, 과제 시작 시간을 분으로 통일한 시간, 과제 마치는 데 걸리는 시간을 필드로 가지는 클래스를 선언한다. 우선순위 큐에 과제 계획을 객체로 저장하여 과제 시작 시간이 빠른 순으로 정렬한다.

 

우선순위 큐가 빌 때까지 다음 과정을 반복한다.  

1) stack이 비어있다면 queue에서 poll 한 값을 저장 및 현재 시간을 과제 시작 시간으로 업데이트한다.

2) 새로운 과제를 시작할 시각이 되었다면 기존에 진행 중이던 과제를 멈추고 새로운 과제를 시작한다. 이때, 과제를 진행한 만큼 과제를 마치는 데 걸리는 시간을 업데이트한다. 현재 시간도 새로운 과제 시작 시간으로 업데이트한다. 

3) 진행 중이던 과제를 끝냈다면 현재 시간을 과제 끝난 시간으로 업데이트하고 answer에 stack에서 pop 한 값의 과제 이름을 저장한다.

 

stack이 빌 때까지 pop 하여 과제 이름을 answer에 순서대로 저장한다. 최종 answer을 반환한다. 

 

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges