비주얼 스튜디오 코드에서 괄호 짝이 맞는지 검사하는 기능을 함수로 구현하시오.

입력은 괄호가 포함된 문자열이고, 출력은 boolean으로 리턴한다.

작성 코드

const balancedBrackets = function (str) {
  // TODO: 여기에 코드를 작성합니다.
  
  //입력: 괄호 포함한 문자열. (테스트 케이스를 보아하니 일단 괄호만 들어가 있네..)
  //출력 : true 또는 false

  //엣지 케이스: 빈 문자열 들어올 경우 true 출력한다. / ( 또는 )가 한개만 들어온 경우 false.
  // str의 길이가 홀수라면 무조건 false. 짝이 안 맞다. 
  //짝수일 때만 위장 false가 있을 수 있으니, 여기서 걸러야 한다.
  
  //일단, 괄호의 종류를 () 이거 하나로 한정.
  //짝이 맞는다는 것은 무슨 뜻인가?
  /*
  짝이 맞는다는 것의 의미
  예시
  () => 0,1: 0번째에는 (   , 1번째에는 ) {o1: 1, c1: 1} open = [1] close = [1]
  )( => 무조건 () 이 순서인데 반대로 와서 탈락함. 
  ())()(() => 앞에서 1번 열렸는데, 그 다음에 2번 닫혀서 탈락. {o1: 1, c1: 2, o2: 1, c2: 1, o3: 2, c3: 1} open = [1,1,2] close = [2,1,1]
  (())()(()) => 앞에서 2번 열리고, 다음으로 2번 닫힘. 1번 열리고 1번 닫힘. 2번 열리고 2번 닫힘 {o1: 2, c1: 2, o2: 1, c2: 1, o3: 2, c3: 2}
  open = [2,1,2] close = [2,1,2]
  (((((((((()))))))))) 앞에서 10번 열리고, 다음으로 10번 닫힘. 
	{o1: 10, c1: 10} open = [10] close = [10]
  필요한 것: 열린 횟수를 저장할 변수와 닫힌 횟수를 저장할 변수. 
  배열로 표현했을 때, 두 배열이 완전 동일해야 같다고 인정할 수 있다. 
	이때 JSON.stringify사용해서 비교해버리자. 
  */
  if(str === '') return true;
  if(str.length % 2 === 1 ) return false;
  //일단 주어진 문자열 하나 하나 다 돌아봐야 한다.(순회)
  //순회하면서 이전 문자도 ( 이고 지금 문자도 ( 이면 open배열의 마지막 요소를 업데이트.
  //이전 문자가 ( 인데 지금 문자가 ) 나오면, close 배열에 1푸시한다.
  //이전 문자도 ) 이고 지금 문자도 ) 이면 close배열의 마지막 요소를 업데이트.
  //이전 문자가 ) 인데 지금 문자가 ( 나오면, open 배열에 1푸시한다.
  //*0번째는 무조건 open 배열에 1 푸시
  //마지막 문자는 지금 규칙 따른다. 
  const open = [];
  const close = [];
  for(let i = 0; i < str.length; i++){
    if(i === 0) open[0] = 1;
    else{
      if(str[i - 1] === "(" && str[i - 1] === str[i]) open[open.length - 1]++;
      if(str[i - 1] === "(" && str[i - 1] !== str[i]) close.push(1);
      if(str[i - 1] === ")" && str[i - 1] === str[i]) close[close.length - 1]++;
      if(str[i - 1] === ")" && str[i - 1] !== str[i]) open.push(1);
    }
  }
  return JSON.stringify(open) === JSON.stringify(close);
};

레퍼런스

스택의 원리를 이용하였다.

일단 여는 괄호가 연속해서 나오는 동안은 쭉 스택에 저장한다. (가장 나중에 저장된 괄호가, 가장 먼저 나온다. 실제 괄호도 그러하다.)

처음부터 닫는 괄호가 나오거나, 중간에 짝이 맞지 않는 엉뚱한 괄호가 나오면 여는 괄호의 짝과 비교해 본 다음 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; //true 리턴 시 "(" 는 false 여야 하는데 true가 나온다.
};

문제로 분석하는 , 스택을 써야 하는 상황?

가장 직전에 들어간 데이터와 방금 막 들어온 최신 데이터를 비교하는 상황.

스택의 push, pop연산은 필수적이다. 관련한 메서드로는 concat, slice, splice등 있다.