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

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

주어진 조건에 따라 순서대로 과제를 수행하여 과제를 마치는 순서를 반환하는 문제

- 연산을 편하게 하기 위해서 시:분 으로 주어진 데이터를 분으로 변경하여 저장

- 시작해야 하는 시간 순서대로 주어지지 않기 때문에, 과제 시작 시간을 기준으로 정렬

- 가장 최근에 멈춘 과제부터 시작해야 함 ( Stack 이용 - 후입선출 )

 

우선순위

1) 과제 시작 : 다음 과제를 시작할 시간이 됐을 때, 현재 과제가 진행중이라면 멈춰 둠

2) 멈춰 둔 과제 : 현재 과제를 마치고 다음 과제까지 시간이 남는다면 가장 최근 멈춰 둔 과제를 수행

 

풀이 순서

1) 첫 우선 순위가 시작해야 하는 과제이므로, 시작 과제를 기준으로 수행

2 - 1) 현재 과제를 끝낼 수 없을 경우 : 현재 과제를 주어진 시간만큼 수행하고, Stack에 담음

2 - 2) 현재 과제를 끝낼 수 있는 경우 : 현재 과제를 다 수행한 남은 여유 시간을 가지고, 멈춘 과제를 수행

3) 마지막 과제를 시작했을 경우 다음 과제가 없기 때문에 무조건 끝까지 수행됨

4) 마지막 과제를 끝낸 경우 가장 최근에 멈춘 과제부터 모든 과제를 수행

 

풀이 과정

using System;
using System.Collections.Generic;

public class Solution
{
    public class DataClass
    {
        public string planName; // 과제 이름
        public int startTime; // 시작 시간
        public int playTime; // 남은 시간

        public DataClass(string planName, int startTime, int playTime)
        {
            this.planName = planName;
            this.startTime = startTime;
            this.playTime = playTime;
        }
    }

    // DataClass를 시작 시간을 기준으로 정렬하기 위한 메서드
    public int CompareTo(DataClass x, DataClass y)
    {
        return (x.startTime < y.startTime) ? -1 : 1;
    }

    public string[] solution(string[,] plans)
    {
        List<string> answerList = new List<string>(); // 완료한 과제
        Stack<DataClass> stack = new Stack<DataClass>(); // 하다가 멈춘 과제
        List<DataClass> list = new List<DataClass>(); // plans[,]

        // 데이터 정제
        for (int i = 0; i < plans.GetLength(0); i++)
        {
            string[] str = plans[i, 1].Split(":");
            int startTime = int.Parse(str[0]) * 60 + int.Parse(str[1]);
            list.Add(new DataClass(plans[i, 0], startTime, int.Parse(plans[i, 2])));
        }

        // 데이터 정렬
        list.Sort((x, y) => CompareTo(x, y));
        
        // 순서대로 과제 시작
        for (int i = 0; i < list.Count - 1; i++)
        {
            // 다음 과제 시작까지 남은 시간
            int nextStartTime = list[i + 1].startTime - list[i].startTime;
            
            // 현재 과제를 끝낼 수 없는 경우
            if(nextStartTime < list[i].playTime)
            {
                list[i].playTime -= nextStartTime;
                stack.Push(list[i]);
                continue;
            }
            
            // 현재 과제를 끝낸 후
            answerList.Add(list[i].planName);
            nextStartTime -= list[i].playTime;
            
            // 여유시간 & 멈춰 둔 과제가 있는 경우 수행
            while(nextStartTime > 0 && stack.Count > 0)
            {
                DataClass dataClass = stack.Pop();
                
                if (dataClass.playTime > nextStartTime)
                {
                    // 멈춰둔 과제를 해결할 수 없음
                    dataClass.playTime -= nextStartTime;
                    nextStartTime = 0;
                    stack.Push(dataClass);
                }
                else // dataClass.playTime <= nextStartTime
                {
                    // 멈춰둔 과제 해결할 수 있음
                    nextStartTime -= dataClass.playTime;
                    answerList.Add(dataClass.planName);
                }
            }
        }

        // 마지막 인덱스 예외처리
        answerList.Add(list[list.Count - 1].planName);

        // 미뤄둔 과제 실행
        while (stack.Count != 0)
            answerList.Add(stack.Pop().planName);

        return answerList.ToArray();
    }
}