[ 소프티어 ] 업무 처리 (C++)

https://softeer.ai/practice/6251

 시간 제한, 메모리 제한이 주어지는 H, K, R의 크기에 비해 널널해서 트리와 큐를 이용해 문제의 요구사항을 정확하게 구현하면 풀 수 있는 문제라고 생각했다.

 

[ 풀이 방법 ]

1. 이진 트리 생성 기능

  - 완전이진트리를 만들어야 하므로 크기가 2^H+1, root의 index가 1인 배열을 생성해 트리를 생성한다.

  - leaf 노드는 큐 1개, 다른 노드는 큐 2개를 이용해 맡은 업무를 저장한다.

      - pair<queue<int>, queue<int>>를 이용해 구현.

      - leaf 노드의 경우 first 큐만 사용하고 다른 노드의 경우 홀수 번째 날짜에는 first 큐, 짝수 번째 날짜인 경우 second 큐를 사용한다.

vector<pair<queue<int>, queue<int>>> tree;
tree.resize(pow(2, H+1));
int leafIdx = pow(2, H);

 

2. 업무 처리 기능

  - root 노드부터 시작해서 모든 노드의 맡은 업무를 처리한 후 부모 노드로 올리는 작업을 수행한다.

      - "그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다." 조건을 만족시키기 위해서,

        부모 노드 -> 자식 노드 순서로 진행한다.

      - 날짜 수를 세서, 날짜가 홀수이면 first 큐의 업무를 처리하고 날짜가 짝수이면 second 큐의 업무를 처리한다.

  - 왼쪽 자식 노드는 부모 노드의 first 큐에 처리한 업무를 삽입한다.

  - 오른쪽 자식 노드는 부모 노드의 second 큐에 처리한 업무를 삽입한다.

  

3. 위 기능을 R번 반복하는 기능

  - R일이 지난 후, 완료된 업무들의 번호의 합을 출력한다.

 

[ 회고 ]

 트리와 큐를 이용한 풀이 방법을 떠올려 구현 계획을 확실히 세운 후 구현하였기 때문에 IDE를 사용하지 않고도 정확하게 구현, 디버깅하여 정답을 맞출 수 있었다.

 

[ 정답 코드 ]

#include<iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <queue>

#define ROOT 1

using namespace std;

int H, K, R;
vector<pair<queue<int>, queue<int>>> tree;

int leafIdx;

int res;
int day;

void work(int i) {
    if(tree[i].first.empty()) return;
    int w = tree[i].first.front();
    if(i%2) tree[i/2].second.push(w);
    else tree[i/2].first.push(w);
    tree[i].first.pop();
}

void workEven(int i) {
    if(tree[i].second.empty()) return;
    int w = tree[i].second.front();
    if(i%2) tree[i/2].second.push(w);
    else tree[i/2].first.push(w);
    tree[i].second.pop();
}

void update() {
    for(int i = ROOT; i < tree.size(); i++) {
        if(i < leafIdx) {
            bool odd = day%2;
            if(odd) work(i);
            else workEven(i);
        } else {
            work(i);
        }
    }
}

void solve() {

    while(++day <= R) {
        update();
    }
    
    while(!tree[0].first.empty()) {
        res += tree[0].first.front();
        tree[0].first.pop();
    }
    while(!tree[0].second.empty()) {
        res += tree[0].second.front();
        tree[0].second.pop();
    }
}

int main(int argc, char** argv)
{
    iostream::sync_with_stdio();
    cin.tie(0);

    cin >> H >> K >> R;
    tree.resize(pow(2, H+1));

    leafIdx = pow(2, H);
    for(int i = leafIdx; i < tree.size(); i++) {
        for(int j = 0; j < K; j++) {
            int t;
            cin >> t;
            tree[i].first.push(t);
        }
    }
    
    solve();

    cout << res << '\n';

   return 0;
}