[자료구조/알고리즘] 211029 괄호짝찾기 #stack이용 #괄호 #reduce

📌 balancedBrackets

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

주의사항

• 괄호의 종류는 (, )만 고려합니다.
• 괄호는 먼저 열리고((), 열린만큼만 닫혀야()) 합니다.
• 빈 문자열을 입력받은 경우, 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(output); // --> false

이건 문제도 이해하는데 10분 걸렸던 거 같다. 그래서 처음엔 진짜 이상한 코드를 내놔서 작성하다가 '이게 아닌데?' 했던거 같다. 근데 웃긴건 테스트 케이스가 부분적으론 통과해서 좀 놀랐다. 그러나 best practice에선 스택을 이용했다.

☑ 처음 접근방법

문자열의 갯수가 0이면 리턴(주의사항 참고). 그리고 문자열의 갯수가 1이라면 어떤 괄호가 들어오든간에 false 리턴. (열기만 했을 뿐 닫히지 않았으니) 이 경우들 일단 제외시켰다. 그래서 작성된 코드가 아래와 같다.

if(str.length === 0) {
    return true
  } else if(str.length === 1) {
    return false
  }
  for(let i=0; i<str.length; i++ ) {
    for(let j=1; j<str.length; j++) {
      if(str[i] === '(' || str[j] === ')') {
        return true
      } else if(str[i] === '{' || str[j] === '}') {
        return true
      } else if(str[i] === '[' || str[j] === ']') {
        return true
      } else {
        return false
      }
    }
  }
}

이중반복문을 돌리면서 열고 닫는 괄호가 있을 때 true 처리를 해주었고, 그게 아니면 false를 리턴. 이렇게 하면 '())()(()' '[(]{)}' '[]}{()' 이 세가지의 경우를 통과하지 못한다.

☑ 두번째 접근방법

그래서 찾은 다른 방법은 reduce를 이용하는 것이었다. 입력받은 문자열과는 별개로 변수에 객체를 할당하는데 키값에 오픈괄호, 밸류값에 클로징괄호를 넣는 것이다. 이 코드는 reduce를 능숙하게 쓰지 못하면 오히려 더 망하는 것 같다.

let bList = { "(" : ")", "{" : "}", "[" : "]" }
let verify = str.split('').reduce(function(ac, cv) {
    if (cv === bList[ac[ac.length - 1]]) {
      ac.pop();
    } else {
      ac.push(cv);
    }
      return ac;
    }, []);
      return verify.length === 0;
    }

반복문에서 괄호 배열의 현재 요소(cv)가 괄호 객체(bList)에 키값으로 존재한다면 빈 배열 verify 맨 뒤에 값을 추가.
키값으로 존재하지 않는 경우에 verify 배열의 맨 마지막 요소의 값을 key로 하여 bList의 value를 찾는다. 현재 요소가 이 value값과 같다면 짝이 맞으므로 verify 배열에서 마지막 요소를 삭제한다.

그러니까 verify가 빈배열이 되면 true를 리턴하게 되는 것이고, 그렇지 않을 땐 false를 리턴하게 되는 것이다.

출처

☑ 레퍼코드

레퍼코드는 위 코드와 방향은 비슷한데 내가 좀 더 이해하기 쉬웠다. 이 코드에서는 3개의 변수를 할당한다. 하나는 스택으로 쓰일 빈 배열, 그리고 키값에 오픈괄호, 밸류값에 클로징괄호를 담은 객체, 마지막으로 클로저 변수를 할당한다.

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

1) 반복문을 돌면서 만약 opener안에 str[i]가 키값으로 있다면 스택에 push
2) 만약 클로저 변수에 str[i]를 포함한다면, opener변수의 가장 top에 있는 것과 str[i]가 일치하지않는다면 false리턴.
3) stack이 빈칸이 된다면 모두 열고 닫음 괄호가 올바르게 일치했다는 것이니 true 리턴.