[C++] 소프티어 [인증평가(5차) 기출] 업무 처리

https://softeer.ai/practice/info.do?idx=1&eid=1256&sw_prbl_sbms_sn=135973 

Softeer

 

업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

 

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

 

부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.

 

풀이

말단 직원은 처음부터 일을 가지고 있고, 나머지 직원들은 왼쪽/오른쪽 직원에게 일을 전달 받기 때문에, 이를 따로 저장할 수 있는 구조체가 필요했다. 이후, 업무를 올리는 과정 후 다음 날로 넘어가는 구조로 코드를 구현했다.

 

1. Info 구조체의 leaf_work는 말단 직원이 가지고 있는 일을 처리하기 위한 큐이다.

2. wf_odd는 왼쪽 직원이 올려준 일을 보관하기 위한 큐, wf_even은 오른쪽 직원이 올려준 일을 보관하기 위한 큐이다.

3. 입력은 벡터 org로 받는다.

 

업무 올리는 과정

1. 부서장의 바로 밑 직원부터 순서대로 상사에게 업무를 올린다. 말단 직원부터 올릴 경우, 거꾸로 가기 때문에 하루만에 모든 일이 올라간다.

2. 말단 직원의 경우, 왼쪽/오른쪽 직원이냐에 따라 상사의 왼쪽 직원이 준 업무(wf_odd), 오른쪽 직원이 준 업무(wf_even) 에 push한다. 이때, 말단 직원 판단은 리프노드의 시작 인덱스이다.

3. 말단 직원이 아닐 경우, 짝수일/홀수일에 따라 업무를 상사에게 올려줘야 한다. 이때, 짝수일의 경우 왼쪽/오른쪽 직원 모두 오른쪽 업무(wf_even)를 상사의 왼쪽/오른쪽 업무(wf_odd/wf_even)에 push 한다. 왼쪽 직원의 오른쪽 업무는 상사에게는 왼쪽 직원이 준 것이기 때문에 왼쪽 업무로 들어간다. 홀수일도 마찬가지이다. (트리를 그려서 이해하자)

4. 부서장의 업무처리는 큐에 들어온 대로 처리하면 된다.

 

리뷰

역시나 소프티어 문제는 감을 잡기가 꽤나 까다롭다... 

큐의 크기를 검사하지 않고 front push pop 한 경우 런타임 에러가 난다. 말단 직원의 경우 모든 일을 전부 올린 경우를 깜빡했다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>

using namespace std;

int H, K, R;

struct Info{
	queue<int> leaf_work;
	queue<int> wf_odd;
	queue<int> wf_even;
};

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

    // freopen("softeer_workprocess.txt", "r", stdin);
	cin >> H >> K >> R;
	int total_node = pow(2,H+1)-1;
	int f_node = pow(2, H);

	vector<Info> org(total_node);

	int leaf_start = total_node-f_node;
	for (int i = leaf_start; i<total_node; i++){
		for (int j=0; j<K; j++) {
			int n;
			cin >> n;
			org[i].leaf_work.push(n);
		}
	}

	int day=1, ans=0;
	int p_node = pow(2, H)-1;

	while (day<=R) {
        // 부서장일 경우 일처리
        if (day%2 != 0 && org[0].wf_odd.size() !=0) {
            ans += org[0].wf_odd.front();
            org[0].wf_odd.pop();
        }
        else if (day%2 == 0 && org[0].wf_even.size() !=0) {
            ans += org[0].wf_even.front();
            org[0].wf_even.pop();
        }
        
        
		// 말단부터 업무 올리기
		for (int i=0; i<p_node; i++){
			int left = i*2+1;
			int right = i*2+2;
			// 말단인 경우 
			if (left >= leaf_start){
                if (org[left].leaf_work.size() != 0){
                    org[i].wf_odd.push(org[left].leaf_work.front());
                    org[left].leaf_work.pop();
                }
                if (org[right].leaf_work.size() != 0){
                    org[i].wf_even.push(org[right].leaf_work.front());
                    org[right].leaf_work.pop();
                }
			}
			// 말단 아닌 경우, 가지고 있는 일이 있다면 짝수/홀수 일에 따라 처리/올리기
			else {
				if (day%2 != 0) {
                    // 홀수날: 왼쪽 직원이 올린 일 처리
                    if (org[left].wf_odd.size() != 0) {
                        // i 노드의 왼쪽 부하직원의 왼쪽 업무를, i노드의 왼쪽 업무에 push(i노드는 왼쪽 직원이 올린 것)
                        org[i].wf_odd.push(org[left].wf_odd.front());
                        org[left].wf_odd.pop();
                    }
                    if (org[right].wf_odd.size() != 0) {
                        org[i].wf_even.push(org[right].wf_odd.front());
                        org[right].wf_odd.pop();
                    }
				}
				else {
                    // 짝수날
                    if (org[left].wf_even.size() != 0) {
                        // i 노드의 왼쪽 부하직원의 오른쪽 업무를, i노드의 왼쪽 업무에 push
                        org[i].wf_odd.push(org[left].wf_even.front());
                        org[left].wf_even.pop();
                    }
                    if (org[right].wf_even.size() != 0) {
                        // i 노드의 오른쪽 부하직원의 오른쪽 업무를, i노드의 오른쪽 업무에 push
                        org[i].wf_even.push(org[right].wf_even.front());
                        org[right].wf_even.pop();
                    }
				}
			}
		}
        // cout << "day: " << day << " " << org[0].wf_odd.front() << " " << org[0].wf_even.front() << endl;
		day++;
	}
	
	cout << ans << endl;

	return 0;
}