TIL17, 코드카타: 괄호 검사!*

어떻게 접근을 해야할지 역대급으로 고민 했던 코트 카타 문제였다. 기억에 남아 여기에 남겨본다.

문제

s는 여러 괄호들로 이루어진 String 인자입니다.
s가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

나의 풀이

1. 주어진 스트링이 (), {}, [] 를 포함하는지 while loop를 통해 반복해서 검사한다.
2. 셋 중 하나라도 포함한다면 스트링에서 해당괄호 부분을 삭제한다.
3. 1번, 2번을 반복하면서, 스트링에서 더 이상 삭제할 것이 없으면 루프를 탈출.
4. 괄호의 순서가 맞지 않았다면 결과로 나온 스트링은 길이가 있을 것이고, 순서가 맞았다면 길이가 없을 것. 이를 이용해서 검사를 한다.

코드는 아래와 같다.

const STR_TO_CHECK = {
  first : "{}",
  second : "()",
  third : "[]"
}

function isValid(s) {
  let stillsomething = true;
  
  while (true) {
    for (let key in STR_TO_CHECK) {
      if (s.includes(STR_TO_CHECK[key])) {
        s=s.replace(STR_TO_CHECK[key], '');
        stillsomething = true;
      } 
    }
    
    if (!stillsomething) break;
    stillsomething = false;
  }

  return ((s.length !== 0)? false : true);
}

나의 풀이 문제점

텍스트 에디터에서 괄호가 잘 닫혔는지에 대해 검사하는 부분에서 쓰일 수 있는 알고리즘인 것 같다. 하지만, 내 접근법은, 단순히 "()", "{}", "[]" 만 찾아서 삭제하는 것이므로, 오늘의 코드카타 문제만 통과를 하는 것에 포커스가 맞춰져 있지, 실제 어딘가에 사용수 있는 그런 코드는 아니다. 단순히 테스트를 통과할 수 있는 풀이법이 과연 의미가 있을까. 앞으로의 코드 카타에서는 그러한 부분을 좀 더 생각하면서 풀이에 접근하자.

모범 풀이

function isValid(s) {
  let matching = {
      '(': ')',
      '[': ']',
      '{': '}'
  };

  let closeArr = [];
  let openArr = [];
  let sArr = s.split('');
  let result = true;

  for (let i = 0; i < sArr.length; i++) {
      let thisStr = sArr[i];
      let closeForOpen = matching[thisStr];
      if (closeForOpen) {
        openArr.push(thisStr);
        closeArr.unshift(closeForOpen);
      } 
      else {
        if (thisStr === closeArr[0]) {
          closeArr.shift();
          openArr.pop();
        } else {
          result = false;
          break;
        }
      }
  }
  
  return result && closeArr.length === 0;
}



//s가 '({})' 라고 가정하겠습니다.
function isValidForCommnet(s) {
  let matching = {
      '(': ')',
      '[': ']',
      '{': '}'
  };

  let closeArr = [];
  let openArr = [];
  let sArr = s.split('');
  let result = true;
  
  //sArr = ['(', '{', '}', ')'] 입니다.
  //sArr을 for문 돌리면서 
  //시작괄호는 openArr에 넣어주고,  ex) openArr = ['(', '{']
  //끝 괄호는 closeArr에 넣어서,    ex) closeArr = ['}', ')']
  //openArr 마지막번째 괄호가 closeArr의 첫번째괄호랑 맞아야 된다는걸 확인하면 됩니다.
  for (let i = 0; i < sArr.length; i++) {
      let thisStr = sArr[i];
      
      //이번 순서의 괄호(thisStr)가 
      //시작괄호-(,[,{- 이라면, matching에 key로 존재하니까
      //closeForOpen가 ) or ] or } 일것이고,
      //끝 괄호라면 undefined 이겠죠.
      let closeForOpen = matching[thisStr];
      
      //thisStr가 시작괄호여서 closeForOpen가 존재한다면,
      if (closeForOpen) {
        
        //openArr에 하나씩 push합니다.
        openArr.push(thisStr);
        //closeArr에는 앞쪽에서 unshift합니다. 
        closeArr.unshift(closeForOpen);
        
      } 
      //closeForOpen가 존재하지 않는다는 뜻은 thisStr가 끝괄호라는 뜻
      else {
        //이번 괄호인 thisStr가 끝괄호면 closeArr에 무조건 첫 번째에 있어야 합니다.
        if (thisStr === closeArr[0]) {
          //제대로 괄호가 여닫기 됐으므로, 
          //closeArr의 첫번째 요소를 제거해주고
          //해당 끝괄호랑 매치되는 openArr의 첫 요소도 제거해줍니다.
          closeArr.shift();
          openArr.pop();
        } else {
          //thisStr가 끝괄호인데, 
          //closeArr의 첫 번째 요소에 있지 않다는 뜻은 제대로 여닫기가 안 된 것이므로
          //for문을 break로 끝내줍니다.
          result = false;
          break;
        }
      }
  }
  
  return result && closeArr.length === 0;
}