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

1. 문제

과제 진행하기

2. 개요

다음과 같은 규칙으로 과제들을 진행하려고 한다.

• 과제는 시작 시각이 되면 시작한다.
• 새 과제를 시작할 시각이 되면, 기존 진행 중이던 과제를 멈추고 새 과제를 시작한다.
• 진행중이던 과제를 끝냈을 때, 멈춰놓은 과제가 있다면 이를 이어서 진행한다.
  • 만약 과제를 끝낸 시각에 새로 시작해야 할 과제와 중간에 멈춰둔 과제가 모두 있다면 새로 시작해야 하는 과제부터 진행한다.
• 멈춰둔 과제가 여럿 있을 경우, 가장 최근에 멈춘 과제부터 이어서 진행한다.

과제마다 과제의 과목명, 시작 시각, 필요 시간이 담긴 이차원 배열이 주어질 때, 과제를 끝낸 순서대로 배열에 담아 이를 출력하는 문제.

3. 풀이 및 코드

3-1. 풀이

시작 시각이 가장 빠른 과제부터 수행하여야 하나 주어진 이차원 배열이 정렬되어있지 않으므로 같은 내용의 리스트를 만들어 시작 시각을 기준으로 오름차순 정리한다.

중간에 멈춰둔 과제들을 담아 둘 공간이 필요한데, 멈춘 과제들 중에 가장 최근에 중지했던 과제를 먼저 다시 진행하여야 하므로 스택을 만들어 둔다.

정렬된 리스트를 탐색하면서 현재 진행할 과제와 다음에 진행할 과제 사이의 시간과 현재 과제의 필요 시간을 비교한다.

만약 필요 시간이 더 길다면, 과제의 인덱스와 필요 시간에서 과제 사이의 시간을 뺀 값을 배열에 담아 스택에 담아둔다. 반대로 필요 시간이 더 짧다면, 바로 정답 배열에 과제 과목명을 추가하고, 과제 사이의 시간에서 필요 시간을 빼 둔다. 남은 시간과 스택의 길이를 고려하면서 중단했던 과제를 스택에서 빼낸다. 모든 과제를 탐색할때까지 이를 반복하고, 답을 출력한다.

3-2. C#

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

public class Solution {
    public string[] solution(string[,] plans) {
        List<string> answer = new List<string>();

        List<List<string>> list = new List<List<string>>();

        for (int i = 0; i < plans.GetLength(0); i++)
        {
            list.Add(new List<string>());

            for (int j = 0; j < plans.GetLength(1); j++)
            {
                list[i].Add(plans[i, j]);
            }
        }

        list.Sort((x, y) => x[1].CompareTo(y[1]));

        Stack<int[]> lefts = new Stack<int[]>();

        for (int i = 1; i <= list.Count; i++)
        {
            if (i == list.Count)
            {
                answer.Add(list[i - 1][0]);
                break;
            }

            List<string> now = list[i - 1];
            List<string> nxt = list[i];

            DateTime startTime = DateTime.ParseExact(now[1], "HH:mm", CultureInfo.InvariantCulture);
            DateTime nextTime = DateTime.ParseExact(nxt[1], "HH:mm", CultureInfo.InvariantCulture);
            int interval = (int)(nextTime - startTime).TotalMinutes;
            int needTime = int.Parse(now[2]);
            int leftTime = interval - needTime;

            if (leftTime < 0)
            {
                lefts.Push(new int[] { i - 1, -leftTime });
            }

            else
            {
                answer.Add(now[0]);

                while (lefts.Count > 0)
                {
                    if (lefts.Peek()[1] > leftTime)
                    {
                        lefts.Peek()[1] -= leftTime;
                        break;
                    }

                    else
                    {
                        int[] leftover = lefts.Pop();
                        leftTime -= leftover[1];
                        answer.Add(list[leftover[0]][0]);
                    }
                }
            }
        }

        while (lefts.Count > 0)
        {
            answer.Add(list[lefts.Pop()[0]][0]);
        }

        return answer.ToArray();
    }
}