[JS]_daily coding #31

seul_·2022년 7월 6일
0

Algorithm

목록 보기
29/31

[SEB FE] Section3 Daily Coding 10_balancedBrackets

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

  • 다음 단계에 맞춰 함수를 작성해 보세요
    1. 괄호의 종류를 단 한가지로 한정합니다.
    2. 괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.
    3. 괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

입력
인자 1 : str
string 타입의 괄호가 포함된 문자열

출력
boolean 타입을 리턴해야 합니다.

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

Advanced
모든 종류의 괄호((, ), {, }, [, ])가 포함된 문자열을 입력빋아 모든 괄호의 짝이 맞는지 여부를 리턴해 보세요.

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

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

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

첫번째 코드

const balancedBrackets = function (str) {
  let lookUp = {};
  for(let i = 0; i < str.length; i++) {
    let ele = str[i];
    lookUp[ele] ? lookUp[ele] += 1: lookUp[ele] = 1;
  }
  return lookUp['('] === lookUp[')'] ? true: false;
}

처음에는 괄호의 짝을 맞추는 경우만 생각해서, 주어진 입력에 ()의 개수를 객체에 따로 저장해서 출현 빈도수만으로 파악했다.문제의 조건인 열린 괄호가 먼저 나오고 그다음 열린만큼 닫혀야한다는 걸 고려하지 못했다.

두번째 코드

나중에 들어온 것이 먼저 빠지는(Last In First Out) 스택 구조를 이용해서 풀었다.
1. 스택을 선언
2. 먼저 입력된 문자열을 순회하는 반복문에서 str의 요소가 열린 괄호인 경우에는 스택에 담는다.
3. 닫힌 괄호가 들어온 경우에는 스택에서 하나를 빼서 비교한다.
3-1. 스택에서 뺀 요소가 열린 괄호가 아닌 경우 - (열림-닫힘)짝을 맞출 수 없는 경우- 에는 false를 리턴한다.
4. 반복문을 빠져나와서 스택에 남아있는 요소가 없다면 모든 괄호의 짝을 찾은 경우이므로 true를 리턴한다.

const balancedBrackets = function (str) {
  const stack = []; 
  for(let char of str) {
    if( char === '(') {
      stack.push(char);
    } else {
        if(stack.pop() !== '(') {
          return false;
        }
    }
  }
  return stack.length === 0? true: false;
}

이렇게 하면, 열린 괄호가 먼저 들어오고 그 다음에 닫힌 괄호가 들어와야한다는 조건을 만족시킬 수 있다.
이제 다음 단계는 {}, []까지 포함한 문자열을 입력받는 경우에 짝이 맞는지 판별할 수 있도록 수정해야 한다.

세번째 코드

열린 괄호일 경우에는 스택에 담아주는 것은 동일하지만, 짝에 맞는 열린 괄호인 경우를 체크해주는 조건이 더 필요하다.

const balancedBrackets = function (str) {
  const stack = []; 
  for(let char of str) {
    //열린 괄호가 들어오는 경우- stack에 담아줌 
    if( char === '(' || char ==='{' || char === '[') {
      stack.push(char);
      continue;
    } 
    
    if( stack.length === 0) return false;
    
    //닫힌 괄호가 들어오는 경우 체크 
    let check = stack.pop(); 
    switch (char) {
      case ')':
        if (check == '{' || check == '[') return false;
        break;
      case '}':
        if (check == '(' || check == '[') return false;
        break;
      case ']':
        if (check == '(' || check == '{') return false;
        break;

    }
  }
  return stack.length === 0? true : false;
};

닫힌 괄호인 경우 종류에 따라 케이스를 나누고, 각각 스택에서 빼낸 값이 괄호 짝이 맞는지를 체크해줬다.

레퍼런스 코드

const balancedBrackets = function (str) {
  const stack = [];
  const opener = {
    '{': '}',
    '[': ']',
    '(': ')',
  };
  const closer = '}])';

  for (let i = 0; i < str.length; i++) {
    if (str[i] in opener) {
      stack.push(str[i]);
    } else if (closer.includes(str[i])) {
      const top = stack.pop();
      const pair = opener[top];
      if (pair !== str[i]) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

레퍼런스 코드는 괄호 짝을 객체로 만들어서 비교를 좀 더 깔끔하게 했다!bb

profile
Connecting dots

0개의 댓글