[소프티어] [인증평가(5차) 기출] 업무 처리 (파이썬) (2)

난이도 : ★★★☆☆

 

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

Softeer

 

📄 문제

• 어떤 부서의 업무 조직은 완전이진트리 모양이다.
• 모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. (포화이진트리)
• 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다.
• 대기하는 업무가 있는 경우, 직원들은 업무가 올라온 순서대로 하나 처리해서 상사에게 올린다.
• 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.
• 부서장이 처리한 일은 완료된 것이다.
• 업무는 R일 동안 진행되며 업무를 올리는 것은 모두 동시에 진행한다.
• 따라서, 그날 올린 업무를 상사가 처리하는 것은 그다음 날에야 가능하다.

 

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

 

---

💡 아이디어

1. 트리 구조를 만들어 준다.
   • 모든 말단 직원은 부서장까지 올라가는 거리가 동일하므로 포화이진트리를 이룬다.
   • root 노드를 인덱스 1로 시작하겠다.
   • 전체 높이가 h이므로 전체 직원의 수는 2^(h+1)-1 명이 된다.
   • i번째 노드의 부모 노드 인덱스는 i / 2이다.
   • i번째 노드의 왼쪽 자식은 i * 2 (짝수), 오른쪽 자식은 i * 2 + 1 (홀수)이다.
2. 업무를 진행하는 R일 동안 홀수 번째 날인지, 짝수번째 날인지 구분해야 한다.
   • 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무 처리
   • 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무 처리
3. 각 직원의 트리에는 부하 직원이 올린 업무 중 처리한 업무만을 저장한다.
   • 즉, 오늘 상사에게 올 릴 수 있는 업무만을 저장한다.
   • 대기하는 업무는 저장하지 않는다.
4. 첫째 날은 처리하지 않는다.
   • 첫째 날은 말단 직원에게서 대기하는 업무가 올라온다.
   • 따라서, 처리될 수 있는 업무가 없으므로 첫째 날은 처리하지 않는다.
5. 둘째 날인 짝수 날부터 시작하고 총 실행 날짜 수는 하루 줄인다.
6. R일이 지나면 tree[1]에 저장되어 있는 부서장이 처리한 업무의 번호를 모두 더해준다. 

---

 

첫 번째 아이디어가 업무를 밑에서부터 올려주며 문제 조건을 그대로 구현했다면,

두 번째 아이디어는 처리 완료된 업무만 부모 트리에서 가져가며 저장하는 좀 더 깔끔한 방법이다.

 

✅ 첫 번째 아이디어

( 실행시간 178 ms, 메모리 41.34 Mb )

https://bu119.tistory.com/32

[소프티어] [인증평가(5차) 기출] 업무 처리 (파이썬) (1)

 

📝 문제 풀이 (Code)

( 실행시간 144 ms, 메모리 39.59 Mb )

import sys
from collections import deque

# 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R
h, k, r = map(int, input().split())

tree = [deque() for _ in range(2**(h+1))]

# 말단 직원 업무 정보 저장
for i in range(2**h, 2**(h+1)):
    tree[i] = deque(map(int, input().split()))

ans = 0

# 처리된 업무를 상사 tree에 저장한다.
# 첫날은 처리될 수 있는 업무가 없으므로 버린다.
# 짝수일 부터 시작하고 날짜 수를 하루 줄인다.
for day in range(r-1):

    # 직원 업무 처리하기
    # 해당 상사가 처리한한 업무를 저장한다.
    for j in range(1,2**h):

        # 홀수 날짜
        if day % 2 == 1:
            # 왼쪽 업무 처리
            if tree[j * 2]:
                tree[j].append(tree[j * 2].popleft())

        # 짝수 날짜
        else:
            # 오른쪽 업무 처리
            if tree[j * 2 + 1]:
                tree[j].append(tree[j * 2 + 1].popleft())

# tree[1]에 부서장이 처리 완료한 업무가 저장되어 있다.
if tree[1]:
    ans = sum(tree[1])

print(ans)