JS Coding Blog

공통 상사를 빠르게 찾기

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

algorithm medium lowest-common-ancestor 함수명: lowestCommonManagerQueries 제한 시간: 500ms

트리에서 두 노드의 가장 가까운 공통 조상을 여러 번 빠르게 찾는 문제입니다.

문제 설명

직원 수 n명인 조직도가 트리 형태로 주어집니다. 직원 번호는 0부터 n - 1까지입니다.

parents[i]는 i번 직원의 바로 위 상사 번호를 뜻합니다.

  • 최고 상사는 부모가 없으므로 -1입니다.
  • 조직도는 하나의 루트를 가진 올바른 트리입니다.

여러 개의 질의 queries가 주어질 때, 각 질의 [a, b]마다 a번 직원과 b번 직원의 가장 가까운 공통 상사 번호를 구해 순서대로 반환하세요.

함수 lowestCommonManagerQueries(n, parents, queries)를 작성하세요.

제한사항

  • 1 <= n <= 200,000
  • parents.length === n
  • parents[root] === -1
  • 루트를 제외한 모든 직원은 부모가 정확히 1명 있습니다.
  • 1 <= queries.length <= 200,000
  • queries[i] = [a, b]
  • 0 <= a, b < n
  • 입력 조직도는 사이클이 없는 트리입니다.

예시

  • 입력: n = 7, parents = [-1,0,0,1,1,2,2], queries = [[3,4],[3,5],[5,6]] → 출력: [1,0,2]
  • 입력: n = 5, parents = [-1,0,0,1,3], queries = [[4,4],[2,4],[1,4]] → 출력: [4,0,1]
  • 입력: n = 6, parents = [-1,0,1,2,3,4], queries = [[5,2],[3,5],[0,5]] → 출력: [2,3,0]

첫 번째 예시에서

  • 3과 4의 공통 상사는 1, 0이 있고 가장 가까운 것은 1
  • 3과 5의 가장 가까운 공통 상사는 0
  • 5와 6의 가장 가까운 공통 상사는 2 입니다.

힌트

  • 질의마다 부모를 한 칸씩 타고 올라가면 최악의 경우 너무 느립니다.
  • 먼저 각 노드의 깊이를 알아 두면 두 노드를 같은 높이로 맞출 수 있습니다.
  • 2^k칸 위 조상을 미리 저장해 두면 여러 칸 점프를 빠르게 할 수 있습니다.

해설

이 문제의 핵심은 LCA(Lowest Common Ancestor) 를 여러 번 빠르게 처리하는 것입니다.

질의마다 부모를 한 단계씩 올리면 트리 높이가 큰 경우 너무 느립니다. 대신 각 노드의

  • 깊이
  • 2^k번째 조상

을 전처리해 두면 각 질의를 O(log n)에 처리할 수 있습니다.

1) 깊이와 점프 테이블 만들기

먼저 루트부터 DFS나 BFS를 하며 각 노드의 깊이를 구합니다.

그리고 up[node][k]를

  • node의 2^k번째 조상

으로 정의합니다.

예를 들어

  • up[node][0] = 바로 부모
  • up[node][1] = 2칸 위 부모
  • up[node][2] = 4칸 위 부모 처럼 채울 수 있습니다.

점화식은 간단합니다.

  • up[node][k] = up[ up[node][k - 1] ][k - 1]

즉, 2^k칸 위는 2^(k-1)칸 위로 두 번 가면 됩니다.

2) 먼저 깊이를 맞추기

두 직원 a, b의 깊이가 다르면 더 깊은 쪽을 위로 끌어올려야 합니다.

깊이 차이를 이진수로 보고 필요한 2^k 점프만 사용하면 한 번에 여러 칸씩 올릴 수 있습니다.

이 과정을 마친 뒤 a === b가 되면, 한쪽이 원래 다른 쪽의 상사였다는 뜻이므로 그 노드가 바로 정답입니다.

3) 가장 높은 서로 다른 조상부터 함께 점프하기

깊이가 같아졌는데 아직 a !== b라면, 두 노드를 가장 큰 k부터 내려오면서 확인합니다.

  • up[a][k] !== up[b][k] 이면
    • 둘 다 그 조상으로 올립니다.

이렇게 하면 두 노드는 정답 바로 아래까지 올라오게 됩니다. 마지막에는 두 노드의 바로 부모가 같아지고, 그 부모가 LCA입니다.

4) 왜 이 방법이 빠를까?

전처리는 O(n log n)이고, 각 질의는 깊이 맞추기와 동시 점프를 합쳐 O(log n)입니다.

질의가 많을수록 한 번 전처리한 뒤 반복해서 빠르게 답할 수 있다는 점이 중요합니다.

5) 구현 포인트

  • 루트의 부모는 -1이므로 점프 테이블에서도 없는 조상 처리를 조심해야 합니다.
  • 같은 노드끼리 묻는 질의는 자기 자신이 정답입니다.
  • 한 노드가 다른 노드의 조상인 경우, 깊이를 맞춘 직후 바로 같은 노드가 될 수 있습니다.

이 문제는 트리 전처리 + 이진 점프 감각을 익히기 좋은 대표적인 알고리즘 문제입니다.

코드 작성

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

JavaScript 에디터 로딩 중...

커스텀 테스트

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

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

실행 결과

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

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

댓글

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