안녕하세요! 이번 포스팅에서는 자바스크립트로 코딩테스트를 준비하는 여러분들을 위해 ‘주몽의 명령’이라는 주제를 가지고 알고리즘 문제를 풀어보겠습니다. 이 과정에서 문제를 이해하고, 접근하는 방법, 코드 구현 및 시간 복잡도 분석까지 자세히 설명할 것입니다.
문제 설명
주몽은 한겨울에도 불구하고 자신의 부하들에게 명령을 내렸습니다. 그의 명령은 다음과 같은 형태로 주어집니다:
- 이진 트리가 주어진다.
- 각 노드는 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 }
결론
이번 포스팅에서는 주몽의 명령이라는 알고리즘 문제를 통해 깊이 우선 탐색과 재귀함수의 개념을 이해하고 구현해보았습니다. 다양한 테스트 케이스를 통해 코드의 신뢰성을 높일 수 있었으며, 각 단계별로 문제를 해결하는 방법을 체계적으로 정리했습니다.
코딩 테스트를 준비하는 과정에서 문제를 접근하는 사고방식과 구현 능력은 매우 중요합니다. 지속적으로 연습하면서 이러한 문제들을 해결하는 데에 익숙해지시길 바랍니다.