[소프티어] 업무 처리 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=1256&sw_prbl_sbms_sn=114405 

Softeer

 

공식 해설: https://softeer.ai/class/algotutor/detail.do?id=85 

Softeer

#include <iostream>
#include <queue>

using namespace std;
typedef long long ll;

queue<int> tree[2048]; // 1부터 1023 까지 노드의 번호로 인덱싱 / 0은 완료된 업무를 담아놓은 큐
int h, k, r;
int n;
ll result = 0;

void process(int x, int day){
	if(x == 0){
		if(!tree[1].empty()){
			tree[0].push(tree[1].front());
			tree[1].pop();
		}
		process(1, day);
	}
	else{
		if(x >= n) return; // 말단사원의 경우 그냥 넘김
		int target = -1;
		if(day % 2 == 1){ // 홀수일이면
			if(!tree[2*x].empty()) target = 2*x; // 왼쪽 자식노드의 업부부터 확인
		}
		else{ // 짝수일이면
			if(!tree[2*x+1].empty()) target = 2*x+1;
		}
		
		if(target != -1){
			// 업무를 target 직원으로부터 받음
			tree[x].push(tree[target].front());
			tree[target].pop();
		}
		process(2 * x, day);
		process(2 * x + 1, day);
	}
}

int main(int argc, char** argv)
{
	cin >> h >> k >> r;

	n = (1 << (h));
	int total = (1 << (h + 1)) - 1;
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < k ; j ++){
			int x;
			cin >> x;
			tree[n + i].push(x);
		}
	}
    
	for(int day = 0 ; day < r ; day ++) {
		process(0, day);
		// for(int i = 0 ; i < (n << 1) ; i ++) cout << i << ' ' << tree[i].size() << '\n';
		
		// cout << '\n';
	}
	
	while(!tree[0].empty()) {
		// cout << tree[0].front() << ' ';
		result += tree[0].front();
		tree[0].pop();
	}
	cout << result;
	return 0;
}

 

위 문제는 5차 인증평가의 기출이다.

 

어떻게 풀 수 있을까?

 

depth가 10까지 올 수 있으므로 완전이진트리의 경우 Depth가 10일 때, 2^11 - 1개의 노드가 필요하다. 그러므로 4047개의 노드가 필요하다. 완전 이진 트리의 경우 배열의 인덱스로만 왼쪽과 오른쪽의 자식노드를 알 수 있다는 장점이 있다.

 

x번째 노드의 왼쪽 노드의 인덱스는 2*x이고 오른쪽 노드의 인덱스는 2*x+1이라는 것은 잘 알려져있다.

 

또한 각각의 노드 데이터를 큐로 구성하여 대기열에 있는 테스크들을 순차적으로 처리할 수 있게끔 구현하였다.

 

처음에는 말단 직원만 작업이 존재하기 때문에 순차적으로 말단노드의 큐에 테스크 번호를 삽입해주도록 하자. 그리고 나서 하루마다 DFS방식으로 순회하며 0번부터 부서장(루트노드: Index=1)부터 말단 직원까지 순회를 하는데 각각의 방문마다 오늘이 홀수날이면 왼쪽자식노드의 테스크가 있는지 (큐가 비었는지) 확인하고 비어있지 않다면 왼쪽노드의 자식노드의 큐의 front를 pop한다음에 내 작업량 큐에 가장 마지막 노드로 삽입한다.

 

루트노드, 즉 여기서는 부서장의 번호는 1부터 시작하는 것으로 하였다. 0번의 노드에는 부서장이 처리한 Task를 가지고 있어 최종적으로 부서장에게 까지 수행이 완료된 task들이 queue에 모여있을 것이다.

 

모든 날이 끝나면 최종적으로 부서장까지 수행이 완료된 task들이 tree[0]에 모두 저장되어 있을 것이다. tree[0]이 빌때까지 front를 털고 털어 result에 값에 더하고 최종 적으로 result를 출력하자! result의 경우 입력이나, 출력 정수의 데이터 범위가 제시되지 않아, long long으로 안전하게 출력하였다.

 

 

지금 생각해보니...

 

맞추긴 하였지만 DFS로 재귀적으로 방문하지 않고도 그냥 for문으로 0번부터 n - 1까지 자식노드의 task를 물려받았으면 속도적으로나 메모리 용량적으로나 더 빠르고 직관적인 것 같다... 5차 인증평가를 직접 실시간으로 풀었는데 여기서 나는 최대로 들어올 수 있는 깊이를 잘못봐 크기를 1024로 설정하고 채점현황에서 메모리 엑세스 문제가 발생한 것을 보았고 아쉽게 5차 인증 평가를 통과하지는 못하였다. 이 실수도 하나의 배움이라고 생각하고 겸손해져야겠다고 생각했다.