CodeKata 4 - W2D3

문제

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

첫번째 풀이

function isValid(s) {
  const list = {
    '(' : 1,
    ')' : -1,
    '{' : 2,
    '}' : -2,
    '[' : 3,
    ']' : -3,
  };
  let order =[];

  if(s.length===0){
    return true;
  }
  
  for(let i = 0; i < s.length-1; i++){
    if(list[s[i]]>0){
      order.push(list[s[i]]);
    } else {
      if(order[order.length-1]===-list[s[i]]){
        order.pop();
      } else {
        return false;
      }
    }
  }
  return true;
}

list라는 객체를 만들어주고 key값으로 각각의 괄호를 넣어준뒤 value값으로 열리는 괄호에겐 양수값을 닫히는 괄호에는 음수값을 넣어주었다.
order라는 빈배열을 만들어주고 일단 첫번째 케이스로 문자열 s가 빈문자열일때 경우를 if문을 이용해 빼주었다.
그 다음으로 for문을 이용해 문자열 s의 index값을 이용하여 각각의 괄호를 list에 key값으로 넣어서 해당하는 value값을 확인하고 그 value값이 양수이면 빈배열 order에 push 메소드를 이용하여 넣어주었다. 만약 value값이 음수인 경우 닫히는 괄호라는 의미이기 때문에 (이때 true가 나오는 케이스들을 생각해 보았는데 가장 마지막으로 열린게 가장 먼저 닫혀야 true가 나올 수 있었다) order에 가장 마지막으로 push된 값과 비교해서 절대값이 같은 경우 마지막으로 열린 괄호와 짝이 맞는 것이므로 그 마지막 요소를 pop 메소드를 이용해서 빼주었다. 짝이 맞지 않는 경우에는 바로 false를 return 해주었다.

두번째 풀이

function isValid(s){
  const list = ['()','{}','[]'];
  let newS = s;
  while(s){
    for (let i=0; i<list.length; i++) {
        if(s.includes(list[i])) {
          newS = s.replace(list[i],'');
        }    
      }
    if(newS != s) {
      s = newS;
    } else {
      return false;
    }
  }
  return true;
}

가장 나중에 열린 괄호의 짝이 가장 먼저 닫혀야 true 케이스가 되므로 true인 경우에는 '()','{}','[]'중에 하나가 반드시 들어가게 된다. 이 케이스들을 배열에 담아주고 주어진 문자열 s를 newS라는 변수에 넣어준다. while문 안에 for문을 이용해서 나올수 있는 케이스들을 미리 담아준 배열안의 요소들이 문자열 s에 있는지 includes 메소드를 이용해 확인해주고 있으면 replace 메소드를 이용해 제거해준다. for문을 빠져나온뒤 newS와 for문을 돌고 나온 s를 비교해서 다른 경우 제거된 값이 있다는 것이기 때문에 s에 newS를 할당해주고 아닌경우 짝이 맞지 않아 제거된값이 없다는 소리이기 때문에 바로 false를 리턴해준다. 이런 과정들을 반복해서 s안의 괄호가 모두 짝이 맞아 제거되면 빈 문자열 s가 while문 조건을 false로 만들기 때문에 while문 밖으로 빠져나가게 되고 그때 true값을 return 한다.

세번째 풀이

function isValid(s) {
    let list = ['()', '{}', '[]']
    if (s == "") {
        return true
    }
    for (let i=0; i<list.length; i++) {
        if(s.includes(list[i])) {
            return isValid(s.replace(list[i],''))
        }
    }
    return false
}

두번째 풀이와 유사하지만 다른점은 while문을 사용하지 않고 for문안에 재귀함수를 이용하여 s가 빈 문자열이 될때까지 함수를 반복해서 실행한다. 함수가 반복적으로 실행되어서 빈문자열이 되면 모두 짝이 맞는 것이므로 이때 true를 return하고 그렇지 않은 경우는 false를 return한다.

=> 재귀함수에 익숙치 않아서 전혀 쓸 생각조차 하지 않다가 백엔드분의 풀이를 보고 알게 된 방법. 익숙한 방법을 이용해서 푸는것도 좋지만 지금까지 써보지 않았던 익숙하지 않은 방법을 이용해서 문제를 풀어보는 것도 새로운 문제가 발생했을때 지금보다 더 다양하게 생각해볼수 있기때문에 필요할 것 같다. React 공부와 더불어서 JS공부도 꾸준히 하자🥲