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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/176962?language=cpp

프로그래머스

 

풀이

문제에 있는 그대로를 구현해주면 되었다.

 

1. 과목 시작 시간을 기준으로 오름차순 정렬

2. 첫 번째 과목부터 마지막 과목을 제외하고 다음 과목 시작 전까지 완료할 수 있는지를 검사

3-1. 만약 완료할 수 있는 경우, answer 배열에 해당 과목 이름 push. 

     a. 만약 다음 과목 시작 전까지 여유 시간이 있고 중간에 멈춘 과목이 있다면 이어서 진행

3-2. 만약 완료할 수 없는 경우, 다음 과목 시작까지 남은 시간을 playtime에서 빼고 해당 과목을 중지 과목 stack에 넣어줌.

4. 마지막 과목은 무조건 완료할 수 있으므로, answer 배열에 push.

5. 중간에 중지한 과목이 들어있는 stack의 원소를 차례로 pop하여 answer 배열에 push.

 

 나의 경우 처음에 문제를 잘못 봐서 stack이 아닌 deque로 구현되어있지만, push_back()과 push_pop()만을 이용하는 것으로 대신하여 구현했다.

 

코드

#include <string>
#include <deque>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int timeToMinutes(const string& timeStr) {
    int hour = stoi(timeStr.substr(0, timeStr.find(':')));
    int minute = stoi(timeStr.substr(timeStr.find(':') + 1));
    return hour * 60 + minute;
}

vector<string> solution(vector<vector<string>> plans) {
    vector<string> answer;
    deque<vector<string>> plans_que;
    int finish_num = 0;
    
    // plans[][1]을 기준으로 오름차순 정렬
    sort(plans.begin(), plans.end(), [](const vector<string>& a, const vector<string>& b) {
        return a[1] < b[1];
    });
    
    int i=0;
    while(finish_num !=plans.size()){
        if(i == plans.size()-1){
            answer.push_back(plans[i][0]);
            break;
        } 
        
        // i번재 과목 시작 시간 
        int crr_start_time = timeToMinutes(plans[i][1]);
        
        // 현재 과목 필요 시간 
        int crr_play_time = stoi(plans[i][2]);
        
        // 다음 과목 시작 시간 
        int next_start_time = timeToMinutes(plans[i+1][1]);
   
        // 만약 현재 과목을 종료할 수 있다면 
        if(next_start_time - crr_start_time >= crr_play_time){
            int left_time = next_start_time - crr_start_time - crr_play_time;
            
            // 종료한 과목 수 증가 
            finish_num++;
            answer.push_back(plans[i][0]);
            i++;
                
            // 만약 이미 진행중이던 과목이 있는 경우 
            if(plans_que.size()!=0){
                while(left_time >0){
                    
                    if(plans_que.size()==0) break;
                    
                    // 가장 먼저 큐에 들어온 과목을 이어서 수행
                    vector<string> crr_plan = plans_que.back();
                    plans_que.pop_back();
                    int crr_left_time = stoi(crr_plan[2]);
                    
                    // 이번 과목을 마무리할 수 있는 경우 
                    if(crr_left_time <= left_time){
                        left_time -= crr_left_time;
                        answer.push_back(crr_plan[0]);
                        finish_num++;
                    }
                    
                    // 이번 과목을 마무리할 수 없는 경우 
                    else{
                        crr_left_time -= left_time;
                        crr_plan[2] = to_string(crr_left_time);
                        plans_que.push_back(crr_plan);
                        left_time = 0;
                    }
                } 
            }
        }
        
        // 현재 과목을 종료할 수 없다면 남은 진행 시간 갱신 
        else{
            crr_play_time -= next_start_time - crr_start_time;
            plans[i][2] = to_string(crr_play_time);
            plans_que.push_back(plans[i]);
            i++;
        }
    }
    
    while(plans_que.size()!=0){
        vector<string> crr = plans_que.back();
        plans_que.pop_back();
        string crr_name = crr[0];
        answer.push_back(crr_name);
    }
    return answer;
}

 

 

---

메모

개인적으로 가장 어려웠던 것은 start 시간을 분 기준으로 변환하여 처리하는 것이었던 것 같다. 구현이 어려운 것은 아니고 해당 함수가 생각이 잘 나지 않아서였는데, 이런 사소한..? 부분을 제외하고는 문제 상황 그대로를 구현하면 되어서 생각보다 어렵지는 않았다. 다른 사람의 풀이를 보면 이 부분을 훨씬 간단하게 풀이한 코드들도 확인할 수 있어서 그런 코드를 참고해보아도 좋을 것 같다.

또 백준과는 다르게 프로그래머스에서는 입력 방식이 고정되어있고 그것을 그대로 이용해야 해서 조금 어렵게 느껴지는 부분도 있는 것 같다. 이건 적응해야 할 것 같다~!!