문제
어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다.
모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.
업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.
부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.
부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.
제약조건
1 ≤ H ≤ 10
1 ≤ K ≤ 10
1 ≤ R ≤ 1,000
입력형식
첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.
그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.
제일 왼쪽의 말단 직원부터 순서대로 주어진다.
출력형식
완료된 업무들의 번호 합을 정수로 출력한다.
입력예제 1
1 1 1
1
2
출력예제 1
0
입력예제 2
1 3 2
9 3 7
5 11 2
출력예제 2
5
나의 풀이
낮은 정답률을 기록하고 있는 문제답게 구현하는데 시간도 꽤 걸리고 생각할 것도 많았다.
트리를 list 형태로 root노드의 index로 1로 하여 생성하였고, 업무처리를 위해 deque를 사용하기로 했다.
날짜에따라 왼쪽자식노드에서 올라온 일과 오른쪽 자식노드에서 올라온 일을 다르게 처리함으로 dict 자료형을 이용해 왼쪽과 오른쪽 각 각 deque를 생성해주었다.
그리고 크게 root 노드, root 노드도 아니고 말단직원의 노드가 아닌 노드들 중간 노드라고 칭하겠다. 마지막으로 말단직원의 노드들의 일을 따로 구현했다.
root 노드는 날짜에 따라 홀수 번째 날에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리하도록 하고, 처리한 값이 result에 더해져 정답을 찾아나가도록 하였다.
중간 노드는 홀수 번째 날에는 왼쪽 부하 직원이 올린 업무를 처리하게 하도록 하는데, tree의 인덱스 번호가 짝수에 해당하는 직원(노드)들은 업무를 처리한 후 상사에게 올릴 때 상사의 왼쪽 deque에 올리도록 하고, tree의 인덱스 번호가 홀수에 해당하는 직원(노드)들은 상사의 왼쪽 deque에 올리도록 하였다. 이부분을 놓쳐 런타임에러가 발생했다.
마찬가지로 짝수 번째 날에도 위의 구현방식을 사용해서 구현했다.
말단 직원 노드들은 자신의 deque가 빌때까지 계속 상사의 노드에 올리도록 하였다. 올릴땐 중간 노드와 마찬가지의 방식을 써서 올린다.
import sys
import math
from collections import deque
H, K, R = map(int,input().split())
result = 0
tree = [dict({"left" : deque([]), "right" : deque([])}) for _ in range(pow(2,H))]
for _ in range(pow(2,H)) :
tree.append(deque(list(map(int,input().split()))))
for i in range(1, R + 1) :
if i % 2 == 0 :
if(len(tree[1]['right']) > 0) :
result += tree[1]['right'].popleft()
for j in range(2, pow(2,H)) :
if(len(tree[j]['right']) < 1) :
continue
else :
if(j % 2 == 0) :
tree[j//2]['left'].append(tree[j]['right'].popleft())
else :
tree[j//2]['right'].append(tree[j]['right'].popleft())
else :
if(len(tree[1]['left']) > 0) :
result += tree[1]['left'].popleft()
for j in range(2, pow(2,H)) :
if(len(tree[j]['left']) < 1) :
continue
else :
if(j % 2 == 0) :
tree[j//2]['left'].append(tree[j]['left'].popleft())
else :
tree[j//2]['right'].append(tree[j]['left'].popleft())
if i <= K :
for k in range(pow(2, H), len(tree)) :
if k % 2 == 0 :
tree[k//2]['left'].append(tree[k].popleft())
else :
tree[k//2]['right'].append(tree[k].popleft())
print(result)시간과 메모리도 여유롭게 성공할 수 있었다.
import sys
import math
from collections import deque
h, k, r = map(int, input().split())
tree = [{'L' : deque([]), 'R' : deque([])} for _ in range(pow(2, h))]
for _ in range(pow(2, h)) :
tree.append(deque(list(map(int, input().split()))))
result = 0
for i in range(1, r + 1) :
if i % 2 == 0 :
if tree[1]['R'] :
result += tree[1]['R'].popleft()
for j in range (2, pow(2, h)) :
if j % 2 == 0 and tree[j]['R'] :
tree[j//2]['L'].append(tree[j]['R'].popleft())
elif j % 2 == 1 and tree[j]['R'] :
tree[j//2]['R'].append(tree[j]['R'].popleft())
else :
if tree[1]['L'] :
result += tree[1]['L'].popleft()
for j in range (2, pow(2, h)) :
if j % 2 == 0 and tree[j]['L'] :
tree[j//2]['L'].append(tree[j]['L'].popleft())
elif j % 2 == 1 and tree[j]['L'] :
tree[j//2]['R'].append(tree[j]['L'].popleft())
if tree[pow(2, h)] :
for k in range (pow(2,h), 2 * pow(2,h)) :
if k % 2 == 0 :
tree[k//2]['L'].append(tree[k].popleft())
else :
tree[k//2]['R'].append(tree[k].popleft())
print(result)다시 한 번 풀어봤다.
