올바른 괄호, balancedBrackets (advanced)

문제

문자열을 입력받아 문자열 내의 모든 괄호의 짝이 맞는지 여부를 리턴해야 합니다.
다음 단계에 맞춰 함수를 작성해 보세요괄호의 종류를 단 한가지로 한정합니다.
괄호의 종류를 늘려 모든 종류의 괄호에도 작동하도록 합니다.괄호를 제외한 문자열이 포함된 경우에도 작동하도록 합니다.

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


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


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

 

입출력 예시

 

let output = balancedBrackets('(');
console.log(output); // // -> false

output = balancedBrackets('()');
console.log(output); // --> true

 

Advanced

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

 

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

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

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

 

 

프로그래머스에서 봤던 문제라 신나가지고 풀었는데, advanced에서 살짝 막혔다.

 

처음에는 stack 배열 안의 요소를

 

stack = [
    []
    []
    []
];

 

이런 식으로 세 개 만들어놓고 ( , )는 stack[0]에서 관리, { , }는 stack[1]에서 관리, [ , ]는 stack[2]에서 관리할 수 있게 하려고 했다.

 

근데 테스트 케이스가 [ ( ] { ) } 이렇게 나오니

닫는 괄호일 때 여는 괄호를 pop해서 배열의 길이를 0으로 만드는 로직이 꼬여버렸다.

 

어째 저째 조건 분기를 해서 풀긴 했는데 마음이 영 찝찝하다. 아래는 내가 작성한 코드다.

 

const balancedBrackets = function (str) {
  const stack = [
    [  ],
    [  ],
    [  ]
  ];
  for (let i = 0; i < str.length; i++) {
    if (stack[0].length === 0 && stack[1].length === 0 && stack[2].length === 0) {
      if (str[i] === ')' || str[i] === '}' || str[i] === ']') return false;
    }
    if (str[i] === ')') {
      if(str[i - 1] === '{' || str[i - 1] === '[') return false;
      stack[0].pop();
    }
    if (str[i] === '}') {
      if(str[i - 1] === '(' || str[i - 1] === '[') return false;
      stack[1].pop();
    }
    if (str[i] === ']') {
      if(str[i - 1] === '(' || str[i - 1] === '{') return false;
      stack[2].pop();
    }

    if (str[i] === '(') { stack[0].push(str[i]); }
    if (str[i] === '{') { stack[1].push(str[i]); }
    if (str[i] === '[') { stack[2].push(str[i]); }
  }
  return stack[0].length === 0 && stack[1].length === 0 && stack[2].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) { 	// str[i]가 여는 괄호면
      stack.push(str[i]);	// stack에 push
    } else if (closer.includes(str[i])) {	// str[i]가 닫는 괄호면
    
      const top = stack.pop();		// stack의 마지막 요소를 꺼내 top에 할당
      const pair = opener[top];		// top과 매치되는 닫는 괄호를 pair에 할당
      if (pair !== str[i]) {		// pair가 현재 str[i]와 다르면
        return false;				// false 리턴
        
        // stack이 [ '(', '[' ] 이고 
        // str[i]가 ')' 이라고 하자.
        
        // top은 '[' 가 되고
        // pair는 ']' 가 된다.
        
        // ']'가 와야할 자리에 ')'가 왔으므로 false
        
      }
    }
  }

  return stack.length === 0;
};

 

stack과 별개로 opener라는 객체를 사용한 점이 눈에 띈다.

'(' 로 열었는데 바로 뒤에 ']'로 닫으면 안 된다는 로직을 사용했다.