알고리즘 연습하기

트리와 관련된 알고리즘은 알고리즘 준비하기 - 이진 트리와 이진 순회 글을 확인하면 된다. 하지만 해당 포스트에서 다룰 내용은 전위 순회, 중위 순회, 후위 순회 배열 중에서 2개가 주어졌을 때 다른 하나의 순회를 찾는 방법이다.

순회와 관련된 내용에서 의문이 있으면 위 포스트를 확인했으면 좋겠다.

👉 문제 확인하기 : BOJ - 트리

위 문제에서는 전위 순회, 중위 순회 값이 주어지고 후위 순회 배열을 찾는 문제이다. 가장 좋은 방법은 직접 전위 순회와 중위 순회를 트리 형태로 그림을 그려가며 규칙을 찾는 것이 좋다.

const callStack = [[0, N - 1, 0, N - 1]];

우선 스택 하나를 생성한다. 초기값으로는 왼쪽부터 전위순회 시작점, 전위순회 종점, 중위 순회 시작점, 중위 순회 종점이다.

while (callStack.length) {
  const [preStart, preEnd, inStart, inEnd] = callStack.pop();

  if (preStart > preEnd || inStart > inEnd) continue;

  const rootNode = preOrderList[preStart];
  result.unshift(rootNode);

  let inRootIndex;
  for (let i = inStart; i <= inEnd; i += 1) {
    if (inOrderList[i] === rootNode) {
      inRootIndex = i;
      break;
    }
  }

  let LeftSize = inRootIndex - inStart;

  callStack.push([preStart + 1, preStart + LeftSize, inStart, inRootIndex - 1]);
  callStack.push([preStart + 1 + LeftSize, preEnd, inRootIndex + 1, inEnd]);
}

스택이 비어있을 때까지 반복문을 진행할 것이다. 흐름은 BFS와 비슷하다. 가장 중요한 것은 루트 노드를 먼저 발견하는 것이다. 비록 구하고자 하는 후위 순회에서 루트는 가장 나중에 배열에 입력되기는 하지만 루트 노드를 기준으로 왼쪽과 오른쪽 트리를 나눌 수 있기 때문에 루트 노드가 기준이 되어야 한다.

따라서 새로운 배열(결과 배열)에는 루트노드부터 unshift해주면 루트가 가장 마지막에 위치하게 된다.

🎯 코드 구현 (JS)

let fs = require('fs');
let input = fs.readFileSync('example.txt').toString().trim().split('\n');

const T = Number(input.shift());

for (let i = 0; i < T; i += 1) {
  const N = Number(input.shift());
  const preOrderList = input.shift().split(' ').map(Number);
  const inOrderList = input.shift().split(' ').map(Number);
  const result = [];

  const callStack = [[0, N - 1, 0, N - 1]];

  while (callStack.length) {
    const [preStart, preEnd, inStart, inEnd] = callStack.pop();

    if (preStart > preEnd || inStart > inEnd) continue;

    const rootNode = preOrderList[preStart];
    result.unshift(rootNode);

    let inRootIndex;
    for (let i = inStart; i <= inEnd; i += 1) {
      if (inOrderList[i] === rootNode) {
        inRootIndex = i;
        break;
      }
    }

    let LeftSize = inRootIndex - inStart;

    callStack.push([preStart + 1, preStart + LeftSize, inStart, inRootIndex - 1]);
    callStack.push([preStart + 1 + LeftSize, preEnd, inRootIndex + 1, inEnd]);
  }

  console.log(result.join(' '));
}

🎯 코드 구현 (JS)