프로그래머스 문제 풀이기능 개발

문제 URL 기능 개발

Contents

1. 문제 지문 파악하기
2. 구르미의 알고리즘 풀이

문제 지문 파악하기

이전과 마찬가지로, 입력을 통해서 문제를 차근히 풀어보도록 하겠습니다. 우선, 문제의 입력을 살펴보시죠.

 

입력:
progresses = [93,30,55]
speeds = [1,30,5]

 

이제 1일이 지났다고 합시다. 그럼 각 기능의 진행 상황을 진행 속도만큼 작업이 이루어집니다. 그러면 상태는 다음과 같습니다.

 

1일 차:
progresses = [94,60,60] (progress[i] += speeds[i])
speeds = [1,30,5]

 

계속해서 반복합니다.

 

2일 차:
progresses = [95,90,65] (progress[i] += speeds[i])
speeds = [1,30,5]

3일 차:
progresses = [96,120,70] (progress[i] += speeds[i])
speeds = [1,30,5]

 

이 때, 2번째 기능은 완성되었습니다. 그러나 문제에 따르면, 이전 기능, 그러니까 먼저 들어온 첫 번째 기능이 마무리 될 때까지 배포될 수 없습니다. 따라서 계속 남습니다. 계속 진행해보죠.

 

4일 차:
progresses = [97,120,75] (progress[i] += speeds[i])
speeds = [1,30,5]

5일 차:
progresses = [98,150,80] (progress[i] += speeds[i])
speeds = [1,30,5]

6일 차:
progresses = [99,180,85] (progress[i] += speeds[i])
speeds = [1,30,5]

7일 차:
progresses = [100,210,90] (progress[i] += speeds[i])
speeds = [1,30,5]

 

이제 드디어 첫 번째 기능이 완성되었습니다. 이 순간 progresses에는 2개의 기능이 모두 완성되어서 배포시킬 수 있습니다. 이 때, answer에 2개를 넣어주면 됩니다.

 

7일 차:
progresses = [90] //완성된 기능 배포
speeds = [5] //완성된 기능 배포
answer = [2] //배포된 기능 개수를 넣어줌

 

이제 마지막 남은 기능이 완성될때까지 진행해봅시다.

 

8일 차:
progresses = [95]
speeds = [5]
answer = [2]

9일 차:
progresses = [100]
speeds = [5]
answer = [2]

 

9일이 되어서야, 세 번째 기능이 완성됩니다. 이 때 배포를 진행하면 다음과 같이 됩니다.

 

9일 차:
progresses = [] //완성된 기능 배포
speeds = [] //완성된 기능 배포
answer = [2, 1] //배포된 기능 개수를 넣어줌

 

그래서 답은 [2, 1]이 됩니다. 이 문제는 결국 들어온 순서대로 나가기 때문에, 큐로 푸는 문제입니다. 여기서 progresses, speeds를 모두 큐로 가정하고 풀면 편합니다.

구르미의 알고리즘 풀이

"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.

 

1. progresses, speeds를 큐로 봅니다.
2. 모든 기능이 배포될 때까지, 즉 progresses가 빌 때까지 다음을 반복합니다.
   1. progresses 길이만큼, 순회하여, 각 기능의 진행 상황을 더해줍니다.
   2. 완성된 기능들이 있으면 배포합니다.
   3. 그 날, 배포된 개수가 0보다 크면 answer에 넣습니다.
3. 특정 날짜에 배포 개수들이 저장된 answer를 반환합니다.

굉장히 쉬우니 바로 코드로 살펴보시죠.

 

PYTHON 코드

def solution(progresses, speeds):
    answer = []
    
    # 1. 모든 기능이 배포될 때까지 반복
    while progresses:
        
        # 1. 각 기능들의 그 날 진행률을 더해줌
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
            
        # 2. 완성된 기능이 있으면 배포함
        cnt = 0
        # 진행 상황이 100 이상이면, 배포 가능함. 이 때, 배포할 때 progresses, speeds 모두 제거해야 함.
        while progresses and progresses[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            cnt += 1
        
        # 3. 배포 개수가 1개라도 있으면, answer에 넣어줌
        if cnt > 0:
            answer.append(cnt)
            
    return answer


if __name__ == "__main__":
    progresses = [93,30,55]
    speeds = [1,30,5]
    result = solution(progresses, speeds)
    print(result)

 

이번엔 CPP 코드입니다. 언어만 바뀐 것이지 알고리즘은 같습니다. 이번엔 vector를 큐로 취급해서 사용했습니다.

 

CPP 코드

#include <string>
#include <vector>

#include <algorithm>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    while (!progresses.empty()) {
        
        for (int i=0; i<progresses.size(); i++) {
            progresses[i] += speeds[i];
        }
        
        int cnt = 0;
        
        while (!progresses.empty() && progresses.front() >= 100) {
            progresses.erase(progresses.begin());
            speeds.erase(speeds.begin());
            cnt += 1;
        }
        
        if (cnt > 0) {
            answer.push_back(cnt);
        }
    }
    
    return answer;
}

int main() {
    vector<int> progresses = {93,30,55};
    vector<int> speeds = {1,30,5};
    auto result = solution(progresses, speeds);
    for_each(result.begin(), result.end(), [](int elem){
        cout << elem << " ";
    });
    cout << endl;
    return 0;
}