C# 과제 진행하기 - Stack / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/176962

 

 

나의 풀이

public class Test
{
    public string name;
    public int start;
    public int remain;

    public Test(string name, string timeStr, string playTimeStr)
    {
        this.name = name;
        string[] splited = timeStr.Split(':');
        start = int.Parse(splited[0]) * 60 + int.Parse(splited[1]);
        remain = int.Parse(playTimeStr);
    }
}

public string[] solution(string[,] plans) 
{
    var answer = new List<string>();
    var willPlayed = new Test[plans.GetLength(0)];
    var holded = new Stack<Test>();

    for(int i = 0; i < plans.GetLength(0); ++i)
        willPlayed[i] = new Test(plans[i, 0], plans[i, 1], plans[i, 2]);

    Array.Sort(willPlayed, (a, b) => a.start < b.start ? -1 : 1);

    int time = 0;
    int startIndex = 0;
    while(startIndex < plans.GetLength(0))
    {
        Test cur = willPlayed[startIndex];

        bool isLast = startIndex + 1 == plans.GetLength(0);
        int availableTime = isLast ? int.MaxValue : willPlayed[startIndex + 1].start - cur.start;

        holded.Push(cur);
        while(holded.Count > 0)
        {
            Test top = holded.Peek();
            if(availableTime >= top.remain) // 시간 충분. 꺼낸 과제완료
            {
                availableTime -= top.remain;
                answer.Add(top.name);
                holded.Pop();

                if(availableTime == 0)
                    break;
            }
            else // 꺼낸 과제를 완료하기에는 시간이 부족함.
            {
                top.remain -= availableTime;
                break;
            }
        }

        ++startIndex;
    }

    return answer.ToArray();
}

컬렉션이 정렬되어있지 않기 때문에 시작 시간 기준으로 정렬먼저 해준 뒤,

하나씩 꺼내서 스택에 넣으면서 다음 과제 전까지 사용가능한 시간을 스택에 있는 과제들을 수행하면 된다.

 

스택에 있는 과제가 모두 소진되면, 다음 과제를 시작하면 되는데,

이때 사이 시간이 비게 되는 경우에는 아무것도 안 하기 때문에 availableTime은 언제나 현재 과제의 시작시간 기준이다.