자바스크립트 코딩테스트 강좌, 주몽의 명령

안녕하세요! 이번 포스팅에서는 자바스크립트로 코딩테스트를 준비하는 여러분들을 위해 ‘주몽의 명령’이라는 주제를 가지고 알고리즘 문제를 풀어보겠습니다. 이 과정에서 문제를 이해하고, 접근하는 방법, 코드 구현 및 시간 복잡도 분석까지 자세히 설명할 것입니다.

문제 설명

주몽은 한겨울에도 불구하고 자신의 부하들에게 명령을 내렸습니다. 그의 명령은 다음과 같은 형태로 주어집니다:

이진 트리가 주어진다.
각 노드는 0부터 n까지의 정수를 담고 있다.
주몽이 명령한 숫자 x가 주어졌을 때, 이진 트리의 모든 경로에서 x의 개수를 세어야 한다.

이 문제에서 우리는 트리의 경로가 무엇인지, 그리고 어떻게 탐색할 것인지를 명확히 이해해야 합니다. 경로란 루트에서 리프 노드까지 이동하는 모든 노드의 집합을 의미합니다.

입력 형식

{
    "root": {
        "value": 1,
        "left": {
            "value": 2,
            "left": null,
            "right": {
                "value": 3,
                "left": null,
                "right": null
            }
        },
        "right": {
            "value": 4,
            "left": null,
            "right": null
        }
    },
    "x": 1
}

출력 형식

주어진 이진 트리에서 숫자 x의 개수를 포함하는 모든 경로의 x 개수의 합을 반환한다.

{
    "result": 2
}

문제 접근법

이 문제를 풀기 위해서는 DFS(Depth-First Search) 알고리즘을 사용할 것입니다. 이진 트리를 깊이 우선으로 탐색하면서 경로를 따라 `x`를 세어 나가는 방식입니다.

1단계: 트리 탐색

우선 트리를 탐색할 수 있는 재귀 함수를 작성합니다. 이 함수는 현재 노드, 현재 경로에 포함된 x의 개수, 그리고 결과를 저장할 변수를 인자로 받습니다.

2단계: 경로 저장 및 조건 확인

노드가 리프 노드인지 확인하고, 리프 노드에 도달했을 때 경로에 포함된 x의 개수를 결과 변수에 더합니다. 그리고 현재 노드가 리프가 아닐 경우 왼쪽 및 오른쪽 자식 노드를 재귀적으로 탐색합니다.

3단계: 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(n)입니다. 트리의 모든 노드를 한 번씩 방문하기 때문입니다.

코드 구현


function countXPaths(root, x) {
    let totalPathsCount = 0;

    function dfs(node, currentCount) {
        if (node === null) {
            return;
        }

        // 현재 노드의 값을 확인
        let newCount = currentCount + (node.value === x ? 1 : 0);

        // 리프 노드인지 확인
        if (node.left === null && node.right === null) {
            totalPathsCount += newCount;
            return;
        }

        // 왼쪽과 오른쪽 자식 노드 탐색
        dfs(node.left, newCount);
        dfs(node.right, newCount);
    }

    dfs(root, 0);
    return { result: totalPathsCount };
}

테스트 케이스

이제 다양한 테스트 케이스를 만들어 우리가 작성한 코드가 예상대로 작동하는지 확인해보겠습니다.


// 1번 테스트 케이스
const testCase1 = {
    root: {
        value: 1,
        left: {
            value: 2,
            left: null,
            right: {
                value: 1,
                left: null,
                right: null
            }
        },
        right: {
            value: 4,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase1.root, testCase1.x)); // 출력: { result: 2 }

// 2번 테스트 케이스
const testCase2 = {
    root: {
        value: 2,
        left: {
            value: 1,
            left: null,
            right: null
        },
        right: {
            value: 1,
            left: {
                value: 3,
                left: null,
                right: null
            },
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase2.root, testCase2.x)); // 출력: { result: 3 }

// 3번 테스트 케이스
const testCase3 = {
    root: {
        value: 5,
        left: {
            value: 1,
            left: {
                value: 1,
                left: null,
                right: null
            },
            right: {
                value: 2,
                left: null,
                right: null
            }
        },
        right: {
            value: 7,
            left: null,
            right: null
        }
    },
    x: 1
};
console.log(countXPaths(testCase3.root, testCase3.x)); // 출력: { result: 2 }

결론

이번 포스팅에서는 주몽의 명령이라는 알고리즘 문제를 통해 깊이 우선 탐색과 재귀함수의 개념을 이해하고 구현해보았습니다. 다양한 테스트 케이스를 통해 코드의 신뢰성을 높일 수 있었으며, 각 단계별로 문제를 해결하는 방법을 체계적으로 정리했습니다.

코딩 테스트를 준비하는 과정에서 문제를 접근하는 사고방식과 구현 능력은 매우 중요합니다. 지속적으로 연습하면서 이러한 문제들을 해결하는 데에 익숙해지시길 바랍니다.