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

난이도 : ★★★☆☆

 

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. 상사는 왼쪽 부하 직원이 올린 업무인지, 오른쪽 부하직원이 올린 업무인지 구분해야 한다.
   • 상사(부모 노드)의 구조는 딕셔너리를 활용한다.
   • 왼쪽, 오른쪽 부하 직원이 올린 업무를 'left', 'right'로 구분하여 저장하겠다.
   • 상사의 인덱스는 현재 인덱스 i / 2로 찾는다.
4. 부서장에게 주어진 일 중 처리 완료한 일을 구분해야 한다.
   • root 노드의 인덱스를 1부터 시작했기 때문에 인덱스 0번에 저장한다. 
   • 업무 진행 날짜가 다 지나고 인덱스 0번에 저장된 업무 번호를 모두 더 해주면 된다.
5. 말단 직원은 오른쪽, 왼쪽 구분이 없다.
   • 트리에 저장할 때 딕셔너리대신 list로 저장하여 따로 계산한다.
   • 매일 하나의 업무를 처리하기 때문에 업무 수 k개만큼만 실행해 주면 된다.
6. 일이 올라온 순서대로 처리해야 한다.
   • deque의 popleft()를 사용하거나 list의 pop(0)를 사용한다.

---

 

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

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

 

✅ 두 번째 아이디어

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

https://bu119.tistory.com/33

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

 

📝 문제 풀이 (Code)

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

import sys
from collections import deque

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

tree = [{'left':deque(), 'right':deque()} for _ in range(2**(h+1))]

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

for day in range(1,r+1):

    # 직원 업무 처리하기
    for j in range(1,2**h):
        v = j // 2
        # 홀수 번째 날, 왼쪽 부하 직원이 올린 처리 건이 있을 때
        if day % 2 == 1 and tree[j]['left']:
            # 상사 기준
            if j % 2 == 0:
                # 상사 기준 왼쪽 부하 직원이 올린 업무 처리 건이면 왼쪽으로 올리기
                tree[v]['left'].append(tree[j]['left'].popleft())
            else:
                # 상사 기준 오른쪽 부하 직원이 올린 업무 처리 건
                tree[v]['right'].append(tree[j]['left'].popleft())

        # 짝수 번째 날, 오른쪽 부하 직원이 올린 처리 건이 있을 때
        elif day % 2 == 0 and tree[j]['right']:
            # 왼쪽 직원 업무 처리건이면 오른쪽으로 올리기
            if j % 2 == 0:
                tree[v]['left'].append(tree[j]['right'].popleft())
            else:
                tree[v]['right'].append(tree[j]['right'].popleft())

    # 말단 직원 업무 처리해서 상사에게 올리기
    if day < k+1:
        for j in range(2**h, 2**(h+1)):
            v = j // 2
 
            if j%2 == 0:
                # 상사 왼쪽 부하 직원 정보에 저장
                tree[v]['left'].append(tree[j].popleft())
            else:
                # 상사 오른쪽 부하 직원 정보에 저장
                tree[v]['right'].append(tree[j].popleft())

print(sum(tree[0]['left']) + sum(tree[0]['right']))