[고득점Kit][큐] 기능개발 ⭐⭐

C++로 풀이했습니다.
출처 : 프로그래머스 고득점 Kit 문제 풀이. https://programmers.co.kr/learn/challenges

[스택/큐] 기능개발

난이도 ⭐⭐

문제

내 풀이

#include <string>
#include <vector>
#include <queue>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    
    queue<int> q;
    
    // 각 작업마다 몇일간 작업 가능한지 계산한 후 큐에 삽입
    // 큐에는 작업마다 소요되는 일 수가 원소로 들어간다.
    for(int i = 0; i < speeds.size(); i++)
    {
        if ((100 - progresses[i]) % speeds[i] == 0)  
            q.push((100 - progresses[i]) / speeds[i]);
        else  // 나머지가 0 이 아닐 땐, 즉 딱 떨어지는게 아닐 땐 1 을 더해주어야 한다.
            q.push((100 - progresses[i]) / speeds[i] + 1);
    }
    
    int count = 0;  
    int temp = q.front();  // 이름을 temp로 잘못 지은 것 같다. 현재까지의 max day 라고 생각하면 됨.
    while (true)
    {
        if (temp >= q.front())
        {
            count++;
            q.pop();
            if (q.empty())
            {
                answer.push_back(count);
                break;
            }
        }
        else
        {
            answer.push_back(count);
            count = 0;
            temp = q.front();
        }
    }
    
    return answer;
}

맨 앞에부터 검사를 해나가며 검사를 끝낸 원소는 삭제할 것이기 때문에 큐가 자료 구조 선택으로 적합하다고 생각 했다.

• 작업마다 소요되는 일 수들이 저장될 큐가 예를 들어 [7 4 3 5 2 8 8 5 6 9]일 때의 answer는 [5, 4, 1]이 된다.
  • 
• 문제에서 주어진 예시
  • 시작
    • 각 작업마다 소요되는 일 수 큐 👉 [7, 3, 9]
    • temp = 7
    • count = 0
  • 7 >= 7
    • 첫번째 작업은 7일차에 배포할 수 있다.
    • count = 1;
    • q.pop() 이후 큐 👉 [3, 9]
    • 큐가 비워진건 아니므로 아직 최종 count 가 결정된 것은 아니다. 아직 answer에 삽입 X
  • 7 >= 3
    • 두번째 작업은 3일차에 배포가 가능하나 첫번째 작업이 7일차에 배포할 수 있으므로 7일차에 첫번째 작업과 같이 배포해야 한다.
    • count = 2;
    • q.pop() 이후 큐 👉 [9]
    • 큐가 비워진건 아니므로 아직 최종 count 가 결정된 것은 아니다. 아직 answer에 삽입 X
  • 7 < 9
    • 7 일보다 더 큰 9 일이 걸리는 작업 등장.
    • 7 일차에 배포하는 작업은 첫번째 작업, 두번째 작업 이렇게로 최종 정리한다.
      • 최종적으로 7 일차에 2 개 배포한다는 의미에서 answer에 2를 삽입.
      • count는 0으로 초기화 해주고
      • 9 를 새로운 temp 로 갱신한다.
    • 이 과정에선 pop연산이 이루어지지 않는다.
  • 9 >= 9
    • 세번째 작업은 9일차에 배포할 수 있다.
    • count = 1;
    • q.pop() 이후 큐 👉 []
    • 큐가 비워졌으므로 answer에 여태까지의 count인 1 삽입 후 while 반복을 끝내야 ㅎ나다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기