[문제 풀이] Softeer "업무 처리"

김준기·2025년 3월 4일

이 포스팅에서는 HSAT 5회 정기 코딩 인증평가 기출 문제 [HSAT 5회 정기 코딩 인증평가 기출] 업무 처리를 다루며, 문제에 접근한 아이디어와 코드 구현에서 왜 이런 선택을 했는지에 대해 설명합니다.

문제 개요

문제 설명

어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다.

모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.

업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

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

입력예제1
1 1 1
1
2
출력예제1
0
입력예제2
1 3 2
9 3 7
5 11 2
출력예제2
5

풀이 접근 및 아이디어

문제의 핵심은 동시에 진행되는 업무 전달 과정을 올바르게 시뮬레이션하는 것입니다. 제가 선택한 접근법의 주요 포인트는 다음과 같습니다.

완전 이진트리 모델링
- 트리의 전체 노드 개수는 (2^(H+1) - 1)이며, 말단(leaf) 노드의 개수는 2^H입니다.
- 부모 노드와 말단 노드를 구분하여, 말단 노드에 초기 업무들을 할당했습니다.
- 파이썬의 음수 인덱싱을 활용해, 리스트의 마지막 부분을 말단 노드(왼쪽, 오른쪽 순서대로)로 사용하였습니다.
업무 대기열 관리 (deque 활용)
- 각 노드별로 처리 대기 중인 업무들을 저장하기 위해 deque를 사용했습니다.
- nodes 배열은 각 노드의 대기 업무를 관리하며,
  left_nodes와 right_nodes 배열은 해당 노드의 왼쪽/오른쪽 부하 직원이 처리한 업무들을 임시 저장합니다.
일자별 업무 처리 시뮬레이션과 시간복잡도
- 1단계: 모든 노드(부서장 포함)를 순회하며,
  - 부서장은 대기 중인 업무가 있다면 이를 처리(즉, 결과에 합산)합니다.
  - 다른 노드들은 보유한 대기 업무에서 맨 앞의 업무를 꺼내어, 자신의 부모 노드의 대기열에 넣습니다.
    - 노드 번호의 홀짝에 따라 왼쪽/오른쪽 부하를 구분하여,
      - 인덱스가 홀수인 경우(i % 2 == 1)는 left_nodes에,
      - 짝수인 경우는 right_nodes에 넣습니다.
- 2단계: 각 부모 노드에서, 조건에 맞는 부하 직원의 업무를 받아 자신의 대기열에 추가합니다.
  - 중요한 포인트:
    업무 전달은 동일한 날에는 재처리되지 않도록 두 단계로 분리되어 있습니다.
    1단계에서 자식 노드의 업무가 상사에게 전달되지만, 그날 바로 상사가 처리할 수 없으므로 2단계에서 상사의 대기열을 준비해 다음 날 처리할 업무를 결정합니다.
- 시간 복잡도:
  - 매일(총 R일) 전체 노드(최대 (2^(H+1)-1))를 순회합니다.
  - 각 노드에서 수행하는 연산은 deque의 popleft()나 append()로 O(1) 시간입니다.
  - 따라서 전체 시간 복잡도는 O(R * 2^(H+1))가 됩니다.
  - 최대 H=10, R=1,000인 경우, 최악의 반복 횟수는 약 1,000 × 2,048 ≒ 2,048,000회로 충분히 빠른 시간 내에 처리할 수 있습니다.
왜 2단계에서 홀수/짝수 날에 반대쪽 대기열을 선택하는가?
- 문제 조건에서는 “홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리”한다고 명시되어 있습니다.
- 하지만, 업무 전달 시뮬레이션에서 주의할 점은 당일 처리한 업무는 바로 재처리되지 않고 다음 날에 처리된다는 것입니다.
- 시뮬레이션 흐름:
  - 1단계: 자식 노드가 처리한 업무는 각 부모 노드의 left_nodes 또는 right_nodes에 저장됩니다.
    - 예를 들어, 완전 이진트리에서 왼쪽 자식(인덱스 1)은 left_nodes에, 오른쪽 자식(인덱스 2)는 right_nodes에 저장됩니다.
  - 2단계: 각 부모 노드는 오늘 받은 업무를 바탕으로, 다음 날 처리할 대기열을 미리 구성합니다.
    - 만약 오늘이 홀수 번째 날이면, 다음 날(짝수 번째 날)에 부서장이 처리할 업무는 “오른쪽 부하 직원이 올린 업무”여야 합니다.
      - 따라서, 2단계에서는 오늘 홀수 날에 부모 노드가 오른쪽 대기열(right_nodes)에서 업무를 꺼내 자신의 대기열에 추가하여, 다음 날 부서장이 처리할 수 있도록 합니다.
    - 반대로, 오늘이 짝수 번째 날이면, 다음 날(홀수 번째 날)에 부서장이 처리할 업무는 “왼쪽 부하 직원이 올린 업무”가 되어야 하므로,
      왼쪽 대기열(left_nodes)에서 업무를 꺼내 추가합니다.
- 결과적으로, 2단계에서의 선택은 다음 날 부서장이 처리해야 하는 업무의 조건(홀수 날은 왼쪽, 짝수 날은 오른쪽)을 맞추기 위해, 현재 날에는 반대쪽 대기열에서 업무를 가져오는 방식으로 구현됩니다.

최종 코드 및 변수 설명

최종 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

from collections import deque

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

# 트리의 노드 개수 및 말단, 부모 노드 수 계산
num_of_nodes = (2 ** (H + 1)) - 1
num_of_edge_nodes = (2 ** H)
num_of_parent_nodes = num_of_nodes - num_of_edge_nodes

# 각 노드의 업무 대기열 (전체 노드 0부터 num_of_nodes-1까지)
nodes = [deque() for _ in range(num_of_nodes)]
# 부모 노드의 좌/우 부하 직원이 올린 업무를 임시 저장할 대기열
left_nodes = [deque() for _ in range(num_of_parent_nodes)]
right_nodes = [deque() for _ in range(num_of_parent_nodes)]

# 말단 노드(리스트의 마지막 num_of_edge_nodes 요소)에 초기 업무 입력 (제일 왼쪽부터 순서대로)
for i in range(num_of_edge_nodes):
    nodes[i - num_of_edge_nodes].extend(map(int, input().split()))

result = 0
# R일 동안 업무 처리 진행
for day in range(1, R + 1):
    # 1단계: 각 노드에서 업무 하나씩 처리 후 상사에게 전달
    for i in range(num_of_nodes):
        # 부서장(노드 0)은 처리한 업무는 완료되므로 결과에 합산
        if i == 0 and nodes[i]:
            result += nodes[i].popleft()
            continue

        if nodes[i]:
            # 해당 노드에서 업무 하나 처리 후, 부모 노드의 대기열에 넣음
            node = nodes[i].popleft()
            parent_i = (i - 1) // 2
            # 노드 번호의 홀짝에 따라 왼쪽/오른쪽 부하를 구분하여 부모의 임시 대기열에 저장
            if i % 2:
                left_nodes[parent_i].append(node)
            else:
                right_nodes[parent_i].append(node)

    # 2단계: 부모 노드에서 조건에 맞는 부하 직원의 업무를 받아 자신의 대기열에 추가
    # → 단, 오늘 처리된 업무는 다음 날에 처리되어야 하므로, 오늘의 선택은 다음 날 부서장이
    #    처리해야 하는 업무의 조건(홀수 날: 왼쪽 부하, 짝수 날: 오른쪽 부하)에 맞추어 준비하는 과정입니다.
    for i in range(num_of_parent_nodes):
        if day % 2:
            # 오늘이 홀수 번째 날 → 내일(짝수 날)에 부서장이 처리할 업무는 오른쪽 부하의 것이어야 함.
            # 따라서, 현재 오른쪽 대기열(right_nodes)에서 업무를 꺼내 부모의 대기열(nodes)에 추가합니다.
            if right_nodes[i]:
                nodes[i].append(right_nodes[i].popleft())
        else:
            # 오늘이 짝수 번째 날 → 내일(홀수 날)에 부서장이 처리할 업무는 왼쪽 부하의 것이어야 함.
            # 따라서, 왼쪽 대기열(left_nodes)에서 업무를 꺼내 부모의 대기열(nodes)에 추가합니다.
            if left_nodes[i]:
                nodes[i].append(left_nodes[i].popleft())

print(result)

변수 설명

H, K, R: 각각 조직도의 높이, 말단 노드당 초기 업무 개수, 업무가 진행되는 날짜 수를 의미합니다.
num_of_nodes: 완전 이진트리의 전체 노드 수.
num_of_edge_nodes: 말단(leaf) 노드의 개수.
num_of_parent_nodes: 부모 노드(말단을 제외한 노드)의 개수.
nodes: 각 노드가 보유한 업무 대기열을 관리하는 리스트.
(말단 노드의 경우, 음수 인덱싱을 통해 리스트의 마지막 부분에 할당)
left_nodes와 right_nodes: 각 부모 노드에 대해 왼쪽/오른쪽 부하 직원이 전달한 업무를 임시 저장하는 대기열.
result: 부서장이 처리한 업무의 번호 합을 저장합니다.

마무리

이번 문제는 동시 진행되는 업무 전달 과정을 올바르게 시뮬레이션하는 것이 관건이었습니다.

deque를 활용해 업무 대기열을 관리함으로써, 효율적인 삽입과 삭제를 구현했으며,
완전 이진트리의 인덱스 특성을 이용하여 부모와 자식 노드 간의 연결을 단순화하였습니다.
시간 복잡도는 매일 전체 노드(최대 2^(H+1)-1개)를 순회하므로, O(R * 2^(H+1))이며, 문제 제약 내에서 충분히 빠른 성능을 보입니다.
2단계 업무 수신에서는 “오늘 처리된 업무가 바로 당일에 재처리되지 않고 다음 날 처리되어야 한다”는 조건에 따라,
- 오늘이 홀수 날이면 내일 부서장이 처리해야 할 업무(오른쪽 부하의 업무)를 미리 준비하기 위해 오른쪽 대기열에서 가져오고,
- 오늘이 짝수 날이면 내일 부서장이 처리해야 할 업무(왼쪽 부하의 업무)를 위해 왼쪽 대기열에서 가져오는 방식으로 설계하였습니다.

이러한 구조 덕분에 문제의 조건을 정확히 반영하면서도, 깔끔한 코드 구성으로 만점 통과할 수 있었습니다.
문제를 풀며 트리 구조의 인덱스 관리, deque를 활용한 효율적 자료구조 사용, 그리고 시뮬레이션 흐름을 면밀히 고민하는 좋은 경험이 되었습니다.

여러분들도 다양한 문제에서 자신만의 아이디어를 적용해보시기 바랍니다!

질문이나 의견은 댓글로 남겨주세요!

김준기

코딩 잘하고 싶은 백엔드 개발자

이전 포스트

[문제 풀이] Softeer "염기서열 커버" – 초염기서열 최소 개수 구하기

다음 포스트

[문제 풀이] Softeer "업무 처리"

문제 개요

풀이 접근 및 아이디어

최종 코드 및 변수 설명

마무리

[문제 풀이] Softeer "염기서열 커버" – 초염기서열 최소 개수 구하기

RESTful API 설계 간단 가이드

0개의 댓글