🧐

이번에는 오롯이 혼자의 힘으로 알고리즘 문제를 풀어봤다
80%정도는 테스트 코드를 다 통과했는데
마지막에 조금 걸렸다😭
그리고 레퍼런스 코드는 몇줄 안되는데 왜 내가 직접짠 코드는 길이가..
알고보니 stack자료구조를 사용하여 풀어야 하는 문제였다
난 아직 문제를 보고 stack을 써야한다는 것을 알 수 있는 내공도 없는 것이다
알고리즘 고수가 되고싶다

🧑‍🏫 문제

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 합니다.

다음 단계에 맞춰 함수를 작성해 보세요

• 괄호의 종류를 단 한가지로 한정합니다.
• 괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
• 괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

주의사항

괄호의 종류는 (, )만 고려합니다.
괄호는 먼저 열리고((), 열린만큼만 닫혀야()) 합니다.
빈 문자열을 입력받은 경우, true를 리턴해야 합니다.

입출력 예시

let output = balancedBrackets('[](){}');
console.log(output); // --> true

output = balancedBrackets('[({})]');
console.log(output); // --> true

let output3 = balancedBrackets('[(]{)}');
console.log(output); // --> false

🖋️ Pseudocode (수도코드, 직접작성)

직접짰지만 테스트 코드는 다 통과 못했다

1. 입력받은 문자열을 각각의 배열의 요소로 쪼개준다
   1-1. 방문한 녀석은 표시해주는 틀을 만든다

2. 중간값을 구한다(짝수라면 왼쪽 녀석이 중간값이 되도록 한다)

3. 선택된 중간값 기준 왼쪽을 순회한다
   3-1. 만약 선택된 녀석이 방문되지 않았고 오른쪽 괄호(')')라면 왼쪽에서 짝('(')을 찾는다
   3-1-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 3을 계속한다
   3-1-2. 만약 짝이 없다면 false를 return한다
   3-2. 만약 선택된 녀석이 방문되지 않았고 왼쪽괄호('(')라면 오른쪽에서 짝(')')을 찾는다
   3-2-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 3을 계속한다
   3-2-2. 만약 짝이 없다면 false를 return한다

4. 선택된 중간값 + 1 기준 오른쪽을 순회한다
   4-1. 만약 선택된 녀석이 방문되지 않았고 오른쪽 괄호(')')라면 왼쪽에서 짝('(')을 찾는다
   4-1-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 4을 계속한다
   4-1-2. 만약 짝이 없다면 false를 return한다
   4-2. 만약 선택된 녀석이 방문되지 않았고 왼쪽괄호('(')라면 오른쪽에서 짝(')')을 찾는다
   4-2-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 4을 계속한다
   4-2-2. 만약 짝이 없다면 false를 return한다

5. 3과 4가 정상적으로 끝나면 true를 return한다

👾 Code

const balancedBrackets = function (str) {
    // TODO: 여기에 코드를 작성합니다.

// 1. 입력받은 문자열을 각각의 배열의 요소로 쪼개준다
const splitStr = str.split('');

// 1-1. 방문한 녀석은 표시해주는 틀을 만든다
let visited = new Array(splitStr.length).fill(false);

// 2. 중간값을 구한다(짝수라면 왼쪽 녀석이 중간값이 되도록 한다)
    let left = 0;
    let right = splitStr.length - 1;
    let middle = parseInt((right + left) / 2);

    // 3. 선택된 중간값 기준 왼쪽을 순회한다
    for(let i = middle ; i > 0 ; i--) {
        //3-1. 만약 선택된 녀석이 방문되지 않았고 오른쪽 괄호(')')라면 왼쪽에서 짝('(')을 찾는다
        if(visited[i] === false && splitStr[i] === ')' || splitStr[i] === '}' || splitStr[i] === ']') {
            let allOfLeft = splitStr.slice(0, middle) //중간값 기준 왼쪽배열을 전부 들고온다

            for(let j = 0 ; allOfLeft.length > j ; j++) { //순회하며 짝('(')을 찾는다
                //3-1-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 3을 계속한다
                if(visited[middle - j] === false && allOfLeft[j] === ')' || allOfLeft[j] === '}' || allOfLeft[j] === ']') {
                    /* 방문표시 해준다 */
                    visited[middle - j] = true;
                } else {
                //3-1-2. 만약 짝이 없다면 false를 return한다
                return false
                }
            }
        }

        //3-2. 만약 선택된 녀석이 방문되지 않았고 왼쪽괄호('(')라면 오른쪽에서 짝(')')을 찾는다
        if(visited[i] === false && splitStr[i] === '(' || splitStr[i] === '{' || splitStr[i] === '[') {

            let allOfRight = splitStr.slice(middle + 1) //중간값 기준 방문되지 않은 오른쪽배열을 전부 들고온다

            for(let j = 0 ; allOfRight.length > j ; j++) { //순회하며 짝(')')을 찾는다'
                //3-2-1. 만약 방문하지 않은 짝이 존재한다면 방문했다는 표시를 해주고 4을 계속한다
                if(visited[middle - j] === false && allOfRight[j] === ')' || allOfRight[j] === '}' || allOfRight[j] === ']') {
                    /* 방문표시 해준다 */
                    visited[middle - j] = true;
                    for(let k = 0 ; allOfRight.length > k ; k++) {
                        if(splitStr[middle - j] === allOfRight[k]) visited[middle + 1 + k] = true;
                    }
                } else {
                //3-2-2. 만약 짝이 없다면 false를 return한다
                return false
                }
                
            }
        }
  };
  return true
}

🖋️ Pseudocode (수도코드, Reference)

1. stack의 틀을 만들어준다
2. 여는 괄호(key)와 닫는 괄호(value)의 짝으로 만들어진 opener객체를 만든다
3. str로 전달받은 문자열을 처음부터 순회하며 요소가 opener에 있는지 closer에 있는지 분기를 만들어 처리한다
   3-1. 만약 순회하는 요소가 opener에 있을 경우 stack에 push한다
   3-2. 만약 순회하는 요소가 closer에 있을 경우 stack의 제일 마지막 요소를 들고와서 짝이 맞는지 확인한다
   3-2-1. 만약 짝이 맞을 경우 3을 계속 순회하고 짝이 맞지 않을 경우 false를 return한다

Reference Code

const balancedBrackets = function (str) {
  const stack = []; //1. stack의 틀을 만들어준다
  
  //2. 여는 괄호(key)와 닫는 괄호(value)의 짝으로 만들어진 opener객체를 만든다
  const opener = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  const closer = '}])';

  //3. str로 전달받은 문자열을 처음부터 순회하며 요소가 opener에 있는지 closer에 있는지 분기를 만들어 처리한다
  for (let i = 0; i < str.length; i++) {
    
     //3-1. 만약 순회하는 요소가 opener에 있을 경우 stack에 push한다
    if (str[i] in opener) {
      stack.push(str[i]);
    } else if (closer.includes(str[i])) {
      
     //3-2. 만약 순회하는 요소가 closer에 있을 경우 stack의 제일 마지막 요소를 들고와서 짝이 맞는지 확인한다
      const top = stack.pop();
      const pair = opener[top];
      
      //3-2-1. 만약 짝이 맞을 경우 3을 계속 순회하고 짝이 맞지 않을 경우 false를 return한다
      if (pair !== str[i]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};