프로그래머스 - 과제 수행하기

문제 설명

과제를 진행하려 한다.

과제를 하던중 새로운 과제가 나오면 새로운 과제를 먼저 해야한다.

과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춘 과제를 진행한다.

또한 멈춘 과제를 진행 중 새로운 과제가 출현하였을 때 새로운 과제를 먼저 해야한다.

그리고 멈춘 과제가 여러개일 경우 최근 멈춘 과제를 먼저 진행한다.

주의사항

과제는 시간순으로 정렬된 상태가 아니므로 정렬한다.

과제를 진행하고 다음 과제 출현 시간 사이에 자투리 시간이 있다면 멈춘과제를 수행해야한다.

즉, 멈춘 과제들을 모두 나중에 처리하는 것이 아님을 인지해야 한다.

여기서의 핵심은 자투리 시간의 과제를 수행해야 한다.

풀이

class Node{
		String name;
		String startTime;
		int playTime;

		public Node(String name,String time, int playTime){
			this.name=name;
			this.startTime=time;
			this.playTime=playTime;
		}

		public int toSeconds(){
			String s[] = startTime.split(":");

			return Integer.parseInt(s[0]) * 60 + Integer.parseInt(s[1]);
		}

		public String toString(){
			return String.format(" <name: %s, startTime: %s, playTime: %d> ",name, startTime, playTime);
		}

		public void minusPlayTime(int val){
			this.playTime -=val;
		}

	}
	public String[] solution(String[][] plans) {
		Stack<Node> waitings = new Stack<>(); // 가장 최근에 멈춘 과제 시작
		LinkedList<Node> works = new LinkedList<>(); // 작업 큐

		for (int i = 0; i < plans.length; i++) {
			works.add(new Node(plans[i][0], plans[i][1], parse(plans[i][2])));
		}

		Collections.sort(works, (a, b) -> a.toSeconds() - b.toSeconds());
		List<Node> answers = new ArrayList<>();
		// 핵심: 잠시 텀이 있으면 최근 과제부터 수행해야 한다.

		int cur = works.get(0).toSeconds();

		while (true) {
			boolean isOperationWaitings = true; // 대기큐를 가동시킬지

			if (!works.isEmpty()) {
				Node work = works.poll();
				if (!works.isEmpty()) {
					Node next = works.peek();
					if (work.toSeconds() + work.playTime <= next.toSeconds()) {
						answers.add(work);
						cur = work.toSeconds() + work.playTime;
					} else {
						// 최근에 들어간 작업은 대기큐에서 검사할 필요가 없기 때문에
						int diff = next.toSeconds() - work.toSeconds();
						work.minusPlayTime(diff);
						cur = next.toSeconds();
						waitings.push(work);
						isOperationWaitings = false;
					}
				} else {
					answers.add(work);
					cur = work.toSeconds() + work.playTime;
				}
			}

			if (isOperationWaitings) {
				// 다음 작업까지 여유가 있다면 웨이팅 큐에서 작업을 한다.
				while (!waitings.isEmpty()) {
					Node rest = waitings.peek();
					if (works.isEmpty()) {
						answers.add(waitings.pop());
					} else {
						Node next = works.peek();
						if (rest.playTime + cur <= next.toSeconds()) {
							answers.add(waitings.pop());
							cur = cur + rest.playTime;
						} else {

							int diff = next.toSeconds() - cur;
							rest.minusPlayTime(diff);
							cur = next.toSeconds();
							break;
						}
					}
				}
			}

			if (works.size() == 0 && waitings.size() == 0) {
				break;
			}

		}

		return answers.stream().map(answer -> answer.name).toArray(String[]::new);
	}

	void print(String s) {
		System.out.println(s);
	}

	int parse(String s) {
		return Integer.parseInt(s);
	}