22. Generate Parentheses
조건에 맞는 모든 괄호쌍 조합을 만드는 문제.
참고: 승지니어 기술면접 라이브코딩 기본편, 예제로 알아보는 백트래킹
백트래킹이 뭔지 확실히 몰라서 승지니어님 영상을 먼저 보고 풀었다.
재귀와 크게 다를 것 없다고..
/**
* @param {number} n
* @return {string[]}
*/
const generateParenthesis = (n) => {
const results = [];
// 생성 함수 정의
const generator = (n, openNum, closeNum, str, results) => {
// 탈출조건; 조건에 맞는 괄호쌍이 완성되면 result에 저장
if (openNum === n && openNum === closeNum) {
results.push(str);
return;
}
// 열린 괄호가 주어진 n 값 미만이면 열린 괄호를 추가
if (openNum < n) generator(n, openNum + 1, closeNum, str + "(", results);
// 닫힌 괄호 수가 열린 괄호 수 미만이면 닫힌 괄호 추가
if (closeNum < openNum)
generator(n, openNum, closeNum + 1, str + ")", results);
};
// 생성 함수 실행
generator(n, 0, 0, "", results);
return results;
};
230. Kth Smallest Element in a BST
BST에서 정렬된 배열을 구하려면, inorder traversy 중위 탐색을 하면 된다.
먼저, 가장 단순하게 중위 탐색으로 배열을 구한 후 k 번째 원소를 가져오는 방식으로 해결했다.
LeetCode에 제출된 답들도 대부분 비슷한 방식으로 구현했다.
근데 왜 어떤 건 시간이 70ms 수준이고 내껀 128ms인걸까..?
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
const kthSmallest = (root, k) => {
// 정렬된 배열 저장하기 위한 빈 배열
const arr = [];
// 중위 탐색하면서 배열에 중위값 저장하는 함수
const inorder = (node) => {
if (!node) return;
const { left, val, right } = node;
inorder(left);
arr.push(val);
inorder(right);
};
// root부터 탐색 시작
inorder(root);
return arr[k - 1];
};최적화
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
inorder 탐색하면 가장 작은 값부터 탐색하게 되므로
아래 코드와 같이 ++i 활용해 k번째 탐색에서 early return 할 수 있다.
근데 runtime beats는 오히려 떨어지는데, 이런 것도 최적화가 맞는 걸까?
- 104 ms => 128 ms
- 44.7 MB => 43.7 MB
const kthSmallest = (root, k) => {
// 저장 순번
let i = 0;
let ans = 0;
// true, false 값을 return하여
// early return에 활용
const inorder = (node) => {
if (!node) return false;
const { left, val, right } = node;
// 재귀를 통해 자식 노드에서 true 값이 return 된 경우 함수 종료
const isTF = inorder(left);
if (isTF) return isTF;
// i번째가 k번째일 경우, 해당 값을 ans에 저장하고 true return
if (++i === k) {
ans = val;
return true;
}
// left와 부분 트리 부모 노드에서 원하는 값이 찾아지지 않는 경우
// right 에서 값 탐색
return inorder(right);
};
// root 노드부터 탐색 시작
inorder(root);
return ans;
};
559. Maximum Depth of N-ary Tree
트리의 최대 깊이 구하기.
BFS 또는 DFS를 통해 구할 수 있다.
트리 전체 길이를 모르는 상황에서는 결국 모든 노드를 탐색해야 하기 때문에,
DFS나 BFS나 시간 복잡도는 동일할 것 같다.
- BFS를 활용해 level 별로 탐색하면서,
- leaf에 도달할 경우 현재까지의 depth를 배열에 저장,
- 배열의 최대값을 return하는 방식으로 구현했다.
/**
* // Definition for a Node.
* function Node(val,children) {
* this.val = val;
* this.children = children;
* };
*/
/**
* @param {Node} root
* @return {number}
*/
const maxDepth = (root) => {
if (!root) return 0;
// 각 leaf의 depth를 저장할 배열
const temp = [];
// BFS로 탐색하면서 depth를 구하는 함수
const getDepth = (node, depth) => {
// node === null 인 경우 예외처리
if (!node) return depth;
// node의 value는 필요없고 자식노드 배열만 가져온다
const { children } = node;
// leaf 노드에서 현재까지의 depth를 배열에 저장 후 종료
if (children.length === 0) {
temp.push(depth);
return;
}
// 자식 노드 배열이 있는 경우
// 자식들에 대해 재귀로 BFS
children.forEach((c) => {
getDepth(c, depth + 1);
});
};
// root 노드, depth===1부터 탐색 시작
getDepth(root, 1);
// 각 leaf depth 중 최대값 반환
return Math.max(...temp);
};
위 코드는 depth+1를 적용하는 부분에서 실수할 수 있고,
그냥 보기에 깔끔하다는 느낌은 없다.
승지니어님 영상을 참고해서 아래와 같이 좀더 BFS다운 정갈한 코드로 리팩토링했다.
참고: 승지니어 기술면접 라이브코딩
LeetCode 결과에서 memory usage는 좀더 증가하는데,
내가 아는 것과는 반대로 LeetCode에서는 while-loop 보다 재귀를 사용할 때 memory usage가 더 증가하는 이상한 결과가 나온다. 왜 그러는 것인지..??
const maxDepth = (root) => {
if (!root) return 0;
let queue = [root];
let depth = 0;
while (queue.length > 0) {
depth++;
const copiedQ = [...queue];
queue = [];
copiedQ.forEach((ele) => {
const { children } = ele;
children.forEach((c) => queue.push(c));
});
}
return depth;
};