[Softeer 인증평가 5차 기출] 업무처리(파이썬)

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

Softeer

 

문제접근

이진트리...

트리...하....

 

 

어려웠던 점

어떻게 작업을 올릴지가 어려웠다.

일반적으로 트리를 만든다면

자식노드까지 잇는 건 많이 해봤는데

자식 노드의 데이터를 올리는 건 잘 해본 적 없었다.

 

힌트

Node를 배열로 받은 다음

Index값에 따라 올려주고 내려준다.

자식노드는 index*2, index*2+1이기 때문에

index//2는 부모노드이므로

업무를 올려줄 때 이를 활용한다.

그림을 그리면 이런 식.

2의 자식노드는

4,5가 되고

3의 자식노드는 

6,7이 된다.

날짜가 홀수,짝수냐에 따라 

각각 올려주면 된다.

 

Node안에는 

job

left

right 

각각 배열을 넣어주었다.

job은 말단직원이 사용하는 배열로

작업을 차례대로 올려줄 때 사용한다.

올려줄 때, 말단직원 index에 따라

상사 left,right중 하나에 저장한다.

left,right는 '상사노드'에서 사용한다.

날짜가 홀수,짝수냐에 따라

리스트 맨 앞의 것을 pop한 다음 처리한다.

(루트노드면 answer에 더해주고, 루트가 아니라면 올려준다)

함수를 재귀적으로 짜는 것이 어렵다.

조건을 잘 설정해서

루트부터 말단노드까지

차례대로 작업을 수행해보자.

 

코드

import sys


def work(index, depth, day):
    global tree, H, answer
    if depth > H:
        return

    # 말단직원이라면 작업물을 올리면 된다
    if depth == H and tree[index].job:
        # 왼쪽 부하라면
        now = tree[index].job.pop(0)
        if index % 2 == 0:
            tree[index // 2].left.append(now)
        # 오른쪽 부하라면
        else:
            tree[index // 2].right.append(now)


    # 부하직원이 있다면 각 작업에 따라 작업물을 올린다
    elif depth < H:
        # 0,2,4-->왼쪽 처리
        if day % 2 == 0 and tree[index].left:
            now = tree[index].left.pop(0)
            if index == 1:
                answer += now
            else:
                if index % 2 == 0:
                    tree[index // 2].left.append(now)
                else:
                    tree[index // 2].right.append(now)
        # 1,3,5-->오른쪽 처리
        if day % 2 == 1 and tree[index].right:
            now = tree[index].right.pop(0)
            if index == 1:
                answer += now
            else:

                if index % 2 == 0:
                    tree[index // 2].left.append(now)
                else:
                    tree[index // 2].right.append(now)

    work(index * 2, depth + 1, day)
    work(index * 2 + 1, depth + 1, day)


# 높이 초기화해주는 함수
def init(index, depth):
    global tree, H
    if depth > H:
        return

    tree[index].depth = depth

    init(index * 2, depth + 1)
    init(index * 2 + 1, depth + 1)


class Node:
    def __init__(self):
        self.depth = 0
        self.left = []
        self.right = []
        self.job = []


H, K, R = map(int, input().split())

# 트리 생성
tree = [Node() for _ in range(2 ** (H + 1))]
init(1, 0)

for i in range(2 ** H, 2 ** (H + 1)):
    data = list(map(int, input().split()))
    # 말단 노드에 데이터 입력해줌
    for d in data:
        tree[i].job.append(d)

# print(tree[2].job)
# print(tree[3].job)

# 하나씩 제귀적으로 돌아가면서 업무를 진행
answer = 0

for day in range(R):
    work(1, 0, day)

print(answer)

참고한 자료

https://velog.io/@hyunjong96/Softeer-%EC%97%85%EB%AC%B4-%EC%B2%98%EB%A6%AC

Softeer - 업무 처리