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

이건 문제도 이해하는데 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를 리턴하게 되는 것이다.