프로그래머스/기능개발(스택,큐)/C++

문제 설명

 

스택/큐 분야로 분류되었던 문제이다. 스택이랑 큐를 쓰지 않고도 풀 수 있다는 게 함정이지만!

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;

    while(true){
        for(int i =0; i<progresses.size(); i++){
        progresses[i] += speeds[i];
        }

        if(progresses[0] >= 100){
            int value = 1;
            for(int j = 1; j<progresses.size(); j++){
                if(progresses[j] >= 100) value++;
                else break;
            }
            answer.push_back(value);
            progresses.erase(progresses.begin(), progresses.begin()+value);
            speeds.erase(speeds.begin(), speeds.begin()+value);
        }
        if(progresses.size() <= 0) break;
    }

    return answer;
}

 

중요한 점

: 앞선 작업이 완료되는 데에 필요한 날 수가 뒷 작업이 완료되는 데에 필요한 날 수보다 많다면, 둘은 앞선 작업이 끝나는 날에 한 번에 배포된다는 것. 작업별로 필요한 날 수를 계산한 다음, 그것끼리 비교해주면 될 일이다.

 

 

 

 

디버깅 기록

: progresses에 speeds만큼 매일매일 더해줘야겠다는 1차원적인 생각 밖에 하지 못했다. 더하기와 빼기의 반복적인 작업을 요구하는 문제에서는 반드시 나누기나 곱하기로 푸는 방법부터 생각해보자. 다른 사람들의 코드를 보며 또 느낀 건, 주어진 자료를 변형(원소 삭제)하여서 문제를 푸는 것은 깔끔하지 못한 방법이라는 것이다. 요즘 알고리즘 문제푸는 것에 자신감이 많이 떨어져서 최대한 구현이 쉽고 단순한 방법으로 풀려고 한 것 같아 아쉽다.

 

나머지를 처리해야 하는 경우에는, 경우의 수를 나누거나 ceil()을 이용하는 방법도 있지만, 아예 식을 조정하는 방법도 있다는 걸 알게 되었다.

ceil((100-progresses[i])/speeds[i]) = (99-progress[i])/speeds[i] + 1