[자료구조/알고리즘] 연습문제 풀기

자료구조 3번

---

문제. 입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.

입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다.
1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다.
2. 열린 괄호는 올바른 순서대로 닫혀야만 한다.
3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.


입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.

입출력 예시

const result1 = isValid('[]');
console.log(result1); // true

const result2 = isValid('[)');
console.log(result2); // false

const result3 = isValid('[]{}()');
console.log(result3); // true

const result4 = isValid('[]{)()');
console.log(result4); // false

풀이

const isValid = (str) => {
  // 최초 입력값이 빈 값이라면 유효하지 않은 괄호쌍으로 간주한다.
  if (str.length === 0) return false;

  // 각각의 여는 괄호에 알맞는 닫는 괄호를 매칭시키기 위한 괄호맵을 생성한다.
  const braketsMap = {
      '(': ')',
      '[': ']',
      '{': '}'
  };

  // split 메서드를 사용하여 str을 공백 문자('')를 기준으로 나누어 배열 arr로 변환한다.
  const arr = str.split('');
  const stack = [];
  
  // 배열의 길이만큼 반복한다.
  for (let i = 0; i < arr.length; ++i) {
      // 1. 여는 괄호 -> stack에 push해야 하는 케이스
      if (arr[i] === '(' || arr[i] === '[' || arr[i] === '{') {
          stack.push(arr[i]);
      } else {
          // 2. 닫는 괄호 -> stack에서 pop해야 하는 케이스
          // 먼저 현재 stack의 가장 위에 위치한 괄호를 확인하고
          const lastElementOfStack = stack[stack.length - 1];
          
          // 지금 처리해야하는 닫힌 괄호인 arr[i]의 짝과 맞는지를 확인 후 맞지 않다면 false를 리턴하고 로직 전체를 종료
          if (braketsMap[lastElementOfStack] !== arr[i]) return false;
          
          // 짝이 맞다면 현재 stack의 가장 위에 위치한 괄호를 pop시켜서 stack에서 제거해줌
          stack.pop();
      }
  }

  // arr 배열전체를 돌면서 해당 로직을 이행한 후 stack에 어떠한 열린괄호라도 남아있다면 쌍이 맞지 않는 괄호들이 인풋으로 들어왔기 때문에 false를 반환, 그렇지 않고 stack이 비어져 있다면 모든 괄호쌍이 문제없이 유효한 괄호쌍이므로 true를 반환
  return stack.length ? false : true;
};

자료구조 5번

---

문제. Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.

입출력 예시

const rootNode = new Tree(null);

for(let i = 0; i <= 4; i++) {
  if(rootNode.children[i]) {
    rootNode.children[i].insertNode(i);
  }
 rootNode.insertNode(i); 
}
rootNode; // {value: null, children: Array(5)}
rootNode.contains(5); // false
rootNode.contains(1); // true
...

풀이

class Tree {
  //tree의 constructor를 구현합니다.
  //tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정합니다.
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  //tree의 자식 노드를 생성 한 후에, 노드의 children에 push해 줍니다.
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  // tree에서 value값을 탐색합니다.
  // 현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
  contains(value) {
    if (this.value === value) {
      return true;
    }
    // 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색합니다.
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }
}

자료구조 8번

---

문제. 이진트리의 root노드를 줄 것입니다. 해당 이진트리의 후위 순회 결과를 출력하세요.

입출력 예시

class TreeNode {
	constructor(val, left, right) {
		this.val = val === undefined ? 0 : val;
		this.left = left === undefined ? null : left;
		this.right = right === undefined ? null : right;
	}
}

//     1
//      \
//       2
//      /
//     3
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
const result1 = postOrderTraversal(root1);
console.log(result1); // [3, 2, 1]

const root2 = null;
const result2 = postOrderTraversal(root2);
console.log(result2); // []

const root3 = new TreeNode(1);
const result3 = postOrderTraversal(root3);
console.log(result3); // [1]

풀이

// 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;
};




// 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;
// };