과제 이름과 시작시간, 그리고 소요시간을 담는 array plan
을 원소로 갖는 array plans
가 주어집니다. 주어진 조건에 따라 과제를 진행할 때 완료되는 순서를 return하는 문제입니다.
멈춰둔 plan
이 여러 개일 경우 가장 최근에 멈춘 plan부터 진행한다는 조건이 있기 때문에, plan을 멈추면 잔여 소요시간과 함께 Stack
에 저장하겠습니다.
프로세스는 다음과 같습니다.
plans
를 시작시간이 빠른 순으로 정렬한다.
각plan
을 읽을 때nextPlan
을 기억해둔다.
멈춰둔 plan
이 있는지stack
을 살펴본다.
stack
이 비어있지 않다면,
꺼내서 잔여 소요시간과plan
의 시작시간을 비교하여 적절히 수행한다.
stack
이 비어있거나stack
에서의 수행을 마쳤다면,
plan
소요시간과nextPlan
의 시작시간을 비교하여 적절히 수행한다.
plans
다 돌면stack
에서멈춰둔 plan
들을 꺼내 완료한다.
적절히 수행한다
는 부분은 현재 보고있는 plan을 완료할 수 있는지 없는지에 따라 doFull
method와 doPartial
method를 만들어 구현했습니다. 또한 시간계산, 정렬 등 구현의 편의를 위해 Plan
class를 만들어 활용했습니다.
import java.util.*;
class Solution {
Stack<Plan> stack = new Stack<>();
List<Plan> planList = new ArrayList<>();
int idx = 0;
int currentTime;
public String[] solution(String[][] plans) {
String[] answer = new String[plans.length];
for (String[] plan : plans) {
planList.add(new Plan(plan));
}
Collections.sort(planList);
currentTime = planList.get(0).start;
for (int i = 0; i < planList.size(); i++) {
Plan cur = planList.get(i);
Plan next;
if (i != planList.size() - 1) {
next = planList.get(i + 1);
} else {
next = new Plan();
next.start = Integer.MAX_VALUE;
}
while (!stack.isEmpty()) {
Plan stacked = stack.pop();
int partial = cur.start - currentTime;
if (stacked.playtime <= partial) {
doFull(stacked, answer);
continue;
}
doPartial(partial, stacked);
break;
}
// case of empty stack
currentTime = cur.start;
int partial = next.start - currentTime;
if (cur.playtime <= partial) {
doFull(cur, answer);
continue;
}
doPartial(partial, cur);
}
while (!stack.isEmpty()) {
answer[idx++] = stack.pop().name;
}
return answer;
}
public void doPartial(int partial, Plan cur) {
currentTime += partial;
cur.playtime -= partial;
stack.add(cur);
}
public void doFull(Plan cur, String[] answer) {
currentTime += cur.playtime;
answer[idx++] = cur.name;
}
class Plan implements Comparable<Plan> {
String name;
int start;
int playtime;
Plan() {}
Plan(String[] plan) {
String[] startHourMinute = plan[1].split(":");
this.name = plan[0];
this.start = Integer.valueOf(startHourMinute[0])
* 60 + Integer.valueOf(startHourMinute[1]);
this.playtime = Integer.valueOf(plan[2]);
}
@Override
public int compareTo(Plan p) {
return this.start - p.start;
}
}
}