문제1. 입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.
입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.
1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.
입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
입력: string 타입으로 된 문장
출력: boolean 타입을 리턴해야 합니다.
const isValid = (str) => {
//입력값을 복사하여 ''를 기준으로 나열하는 배열
//빈 배열을 생성성
let arr = str.split('');
let stack = [];
//arr에 들어있는게 없으면 false 반환환
if(arr.length === 0) {
return false
}
//반복문을 통하여 arr의 길이만큼 순회하며
//(, [, {인 경우 만들어둔 빈 배열에 push
for(let i = 0; i < arr.length; i++) {
if(arr[i] === "(" || arr[i] === "[" || arr[i] === "{") {
stack.push(arr[i])
}
// 만약 ) 일때 stack 배열에 넣어준 값을 꺼내서 (이 아니면 false
else if(arr[i] === ")") {
let open = stack.pop()
if(open !== "(") {
return false
}
}
// 만약 ] 일때 stack 배열에 넣어준 값을 꺼내서 [이 아니면 false
else if(arr[i] === "]") {
let open = stack.pop()
if(open !== "[") {
return false
}
}
// 만약 } 일때 stack 배열에 넣어준 값을 꺼내서 {이 아니면 false
else if(arr[i] === "}") {
let open = stack.pop()
if(open !== "{") {
return false
}
}
}
//stack의 길이가 없으면 flase
if(stack.length !== 0) {
return false;
}
//위 경우에 걸리지 않았다면 true
return true;
}문제2. Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드
insertNode(value) {
// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요
// 트리에 붙게 될 childNode를 만들고, children에 넣기
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드
contains(value) {
//값이 포함되어 있다면 true를 반환
if (this.value === value) return true;
//값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색
for (let childNode of this.children) {
if (childNode.contains(value)) return true
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환
return false;
}
}문제3. 이진트리의 root노드를 줄 것입니다. 해당 이진트리의 후위 순회 결과를 출력하세요.
입력: TreeNode 타입으로 된 root 노드
출력: number[] 을 리턴해야 합니다.
// Definition for a binary tree node.
// class TreeNode {
// constructor(val = 0, left = null, right = null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 1. 재귀적 풀이법
const postOrderTraversal = (root) => {
// 출력결과를 저장하기 위한 result 배열을 하나 만들기
let result = [];
// 트리를 재귀적으로 순회하기 위한 재귀함수를 생성
const dfs = (node) => {
// 재귀의 기저조건으로 방문한 노드가 빈 노드일 경우에 해당 재귀를 종료시킨 후 상위로 올리기
if (node === null) return;
// 트리를 후위 순회하는 것이기 때문에 node를 root로 보았을 때,
// node 기준으로 왼편 -> 오른편 -> 해당 node 순으로 방문
dfs(node.left);
dfs(node.right);
result.push(node.val);
}
// 순회 시작을 위해 최초 받은 root노드를 매개변수로 넣어 재귀함수를 실행
dfs(root);
// 재귀가 모두 끝난 이후 결과를 반환
return result;
};// Definition for a binary tree node.
// class TreeNode {
// constructor(val = 0, left = null, right = null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 2. 반복문적 풀이법
const postOrderTraversal = (root) => {
const stack = [];
const result = [];
if (root === null) return result;
stack.push(root);
while (stack.length) {
const node = stack.pop();
// 후위순회는 root노드의 값이 항상 가장 마지막에 방문되어야 하고, 그 말은 즉 출력결과에 뒷 편에 위치해야 하므로
// 매번 root노드의 값을 출력결과의 맨 앞 부분에 넣어주게 되면 반복문을 돌면서 해당 값이 뒤로 밀리면서 출력결과의 뒷 편에 위치하게 된다.
result.unshift(node.val);
// 후위순회이기 때문에 방문순서는 left -> right -> root이지만,
// 윗 줄의 코드에서 매번 root노드의 값을 출력결과 배열의 맨 앞에 넣어주면서 해당 값을 뒤로 밀어내고 있기 때문에
// 다음 방문을 위한 node의 자식을 stack에 담을 때는 기존 순서대로 left -> right순으로 담아주면 된다.
node.left && stack.push(node.left);
node.right && stack.push(node.right);
}
return result;
};
개발자 동동