JS Coding Blog

하위 조직 보너스 포인트 질의

자바스크립트 코딩테스트 문제로 euler-tour-subtree-query 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard euler-tour-subtree-query 함수명: subtreeBonusPointQueries 제한 시간: 500ms

조직도에서 어떤 매니저의 하위 조직 전체에 보너스 포인트를 더하고, 특정 직원의 현재 포인트를 빠르게 조회하는 문제입니다.

직원은 1번부터 n번까지 번호가 붙어 있습니다. 1번은 대표이며, parents[i - 2]는 i번 직원의 직속 상사입니다.

operations는 다음 두 형태 중 하나입니다.

  • ["add", manager, bonus]: manager와 그 모든 하위 직원의 포인트에 bonus를 더합니다.
  • ["get", employee]: employee의 현재 포인트를 결과 배열에 추가합니다.

모든 get 결과를 순서대로 담은 배열을 반환하는 subtreeBonusPointQueries 함수를 작성하세요.

제한사항

  • 1 <= n <= 200,000
  • parents.length === n - 1
  • parents[i - 2]는 1 이상 i - 1 이하의 정수입니다.
  • initialPoints.length === n
  • -1,000,000 <= initialPoints[i] <= 1,000,000
  • 1 <= operations.length <= 200,000
  • operations의 첫 값은 "add" 또는 "get"입니다.
  • "add"의 bonus는 -1,000,000 이상 1,000,000 이하의 정수입니다.
  • 반환값은 각 "get" 연산의 답을 순서대로 담은 배열입니다.

예시

  • 입력: n = 5, parents = [1, 1, 2, 2], initialPoints = [10, 20, 30, 40, 50], operations = [["add", 2, 5], ["get", 4], ["get", 3], ["add", 1, -10], ["get", 2], ["get", 5]] -> 출력: [45, 30, 15, 45]
  • 입력: n = 4, parents = [1, 2, 3], initialPoints = [0, 0, 0, 0], operations = [["get", 1], ["add", 3, 7], ["get", 2], ["get", 4], ["add", 1, 1], ["get", 3]] -> 출력: [0, 0, 7, 8]
  • 입력: n = 1, parents = [], initialPoints = [100], operations = [["add", 1, -30], ["get", 1], ["add", 1, 5], ["get", 1]] -> 출력: [70, 75]

힌트

  • 트리에서 어떤 노드의 하위 조직은 DFS 진입 순서 기준으로 하나의 연속 구간이 됩니다.
  • 구간 전체에 값을 더하고 한 점의 누적값만 조회하면 되는 구조를 떠올려 보세요.

해설

먼저 조직도를 인접 리스트로 만들고 대표 1번부터 DFS를 수행합니다. 각 직원 x에 대해 DFS에 처음 들어간 시각을 tin[x], 하위 조직을 모두 방문하고 난 뒤의 마지막 시각을 tout[x]라고 하면, x의 하위 조직 직원들은 펼쳐진 배열에서 [tin[x], tout[x]] 구간에 정확히 모입니다.

이제 "add", manager, bonus는 펼쳐진 배열의 [tin[manager], tout[manager]] 구간에 bonus를 더하는 작업으로 바뀝니다. Fenwick Tree를 차분 배열처럼 사용하면 구간 가산을 add(tin, bonus), add(tout + 1, -bonus) 두 번으로 기록할 수 있습니다.

"get", employee는 tin[employee] 위치까지의 누적합을 구하면 지금까지 이 직원에게 적용된 모든 보너스 변화량을 알 수 있습니다. 여기에 initialPoints[employee - 1]을 더한 값이 현재 포인트입니다.

DFS 전처리는 O(n), 각 연산은 Fenwick Tree 갱신 또는 조회 한 번이라 O(log n)에 처리됩니다. 전체 시간 복잡도는 O((n + q) log n), 공간 복잡도는 O(n)입니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.