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

프로그래머스

 

📄 문제

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다.
과제는 시작하기로 한 시각이 되면 시작합니다.
새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.
진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.
만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.
멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.
과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

 

📝 풀이

#include <string>
#include <vector>
#include <unordered_map>
#include <stack>
#include <algorithm>

using namespace std;

struct plan
{
    string name;
    int start;
    int playtime;
    
    plan(){}
    
    plan(string n, string s, string p)
    {
        name = n;
        start = stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2));
        playtime = stoi(p);
    }
    
    const bool operator < (const plan& ref) const
    {
        return start < ref.start;
    }
};

vector<string> solution(vector<vector<string>> plans) {
    
    vector<plan> v; // 입력된 plan 관리
    unordered_map<string, int> m; // 정렬된 v에 대한 인덱스 번호 저장
    for(vector<string> s : plans)
        v.push_back({s[0], s[1], s[2]});

    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i)
        m[v[i].name] = i;
    
    stack<string> s;
    
    vector<string> answer;
    
    // 과제 검사
    for(int i = 0; i < v.size(); ++i)
    {
        int gap;
        if(i + 1 == v.size())
            gap = 1000000;
        else
            gap = v[i + 1].start - v[i].start;
        
        if(v[i].playtime <= gap) // 즉시 해결 가능한경우 ?
        {
            gap -= v[i].playtime; // 남은 시간 차감
            v[i].playtime = 0; // v[i]의 남은 시간은 0
            
            answer.push_back(v[i].name); // 즉시 정답에 삽입
            
            // 아직도 시간이 남은경우?
            while(gap > 0 && !s.empty())
            {
                plan top = v[m[s.top()]]; // 가장 최근에 삽입한 과제 가져오기
                
                if(top.playtime <= gap) // 남은 시간으로 해결 가능한경우 ?
                {
                    gap -= top.playtime; // 남은 시간 재계산
                    top.playtime = 0; // 최근 과제는 종료
                    answer.push_back(top.name); // 정답에 삽입
                    s.pop(); // 과제 제거
                }
                else // 남은 시간으로 해결 불가능한경우
                {
                    // !!!
                    // plan top을 변경하는것이 아닌, 실제 값을 바꿔야 함!!
                    // !!!
                    v[m[s.top()]].playtime -= gap; // playtime만 갱신
                    break;
                }
            }
        }
        else // 즉시 해결하지 못하는경우 ?
        {
            v[i].playtime -= gap; // 시간 소모
            s.push(v[i].name); // 나중에 할 과제에 추가
        }
    }
    
    return answer;
}

• 문제 해결을 위한 접근 방법은 옳았으나, 구조체의 copy의 값을 수정하는 문제로 일부 테스트케이스에서 오답처리가 되었습니다.
• substr(startIdx, length)를 이용하여 동일한 규칙의 문자열을 숫자로 변환하여 시간을 계산합니다.
• start를 오름차순하여 차례대로 과제를 수행합니다.

 

else // 남은 시간으로 해결 불가능한경우
{
    v[m[s.top()]].playtime -= gap; // playtime만 갱신
    break;
}

• playtime을 갱신할 때 copy가 아닌 실제 값을 변경해야 문제가 없는것을 발견하여 수정하여 해결하였습니다.