Stack 문제를 풀고 난 후 ,,

Stack 에 대해 공부를 하고 Stack 문제로 유명한 유효한 괄호쌍 문제를 풀어보았다. 

사실 예전에 비슷한 문제를 풀어본 적이 있어서 수월하게 풀 수 있을 줄 알았는데 1시간정도가 걸렸던 것 같다... 

너무 기만했던 거 같고 다시 한번 풀어보면서 정리를 해봐야겠다. 

문제는 코드스테이츠에서 제공하는 코플릿 문제를 풀었다.  ( 아래에 해결과정과 느낀점이 있습니다 ) 

 

문제 설명 

입력된 괄호 값들이 모두 쌍이 맞게 올바른지를 판단해 모두 쌍이 맞으면 true 그렇지 않으면 false를 출력하세요.

입력된 괄호 값들이 유효한 경우들은 다음에 해당합니다. 1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀있어야 한다. 2. 열린 괄호는 올바른 순서대로 닫혀야만 한다. 3. 모든 닫힌 괄호는 그에 상응하는 같은 타입의 열린 괄호를 갖고 있다.

입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.

입력

인자 1 : str

• string 타입으로 된 문장

출력

• boolean 타입을 리턴해야 합니다.

주의 사항

• 입력값을 통해 들어오는 괄호는 ()[]{}로만 이루어져 있습니다.
• 입력값으로 들어오는 str의 길이는 0부터 10^4승 까지 입니다.

입출력 예시

const result1 = isValid('[]');
console.log(result1); // true

const result2 = isValid('[)');
console.log(result2); // false

const result3 = isValid('[]{}()');
console.log(result3); // true

const result4 = isValid('[]{)()');
console.log(result4); // false

 

나의 풀이 

const isValid = (str) => {
  const stack = [];
  let top = stack.length -1 ; 

  for(let i =0;i<str.length; i++){
    if(str[i]==='(' || str[i]==='[' || str[i]==='{' ){ 
      stack.push(str[i])
      top ++;
    }
    else if(stack.length > 0){ 
     if(str[i]===')'){ 
        if(stack[top]!=='('){
          return false;
        }
        stack.pop();
        top--;
      }
      else if(str[i]===']'){
        if(stack[top]!=='['){
          return false;
        }
        stack.pop();
        top--;
     }
      else if(str[i]==='}'){
        if(stack[top]!=='{'){
          return false;
        }
        stack.pop();
        top--;
      } 
    }
    else{
      return false;
    }
   
  }
  
    if(str.length > 0 && stack.length === 0 ){
      return true 
    }
    else{
      return false;
    }
  }

 

페어분의 도움을 받아 오류를 해결하고 문제를 푸는데 성공하긴 했지만 .. 뭔가 코드가 마음에 들지 않고 지저분하다는 생각이 들었다. 

그래서 새롭게 다시 코드를 생각해보았다. 

 

const isValid = (str) => {
  let openStack = [] ; 
  
  let bracket = {
    '(':')',
    '{':'}',
    '[':']',
  }
  if(str.length === 0){
    return false;
  }
  for(let i =0 ; i< str.length; i++){
    if(str[i] === '(' || str[i] ==='{' || str[i] ==='['){
      openStack.push(str[i]);
    }
    else {
      let top = openStack.length-1;
      if(bracket[openStack[top]]!==str[i]){
        return false;
      }
      openStack.pop();
     
 }
  }
  if(openStack.length===0){
    return true;
  }
  else{
    return false;
  }
}

 

두번째 짠 코드는 barcket이라는 맵을 만들어 열린 괄호를 키로 닫힌 괄호를 값으로 두고 for 문을 실행하여 열린 괄호 일 때는 stack에 push 해주고 닫힌 괄호가 나올 때 현재 최상단에 있는 즉 마지막에 들어온 괄호값을 가리키는 인덱스인 top 변수를 만들어 bracket 의 키로 조회하여 들어온 값이 한 쌍이 아닐 때 false 를 반환해주고 그렇지 않은 경우에는 pop 을 해주어 한쌍을 제거해준다. 그렇게 모든 for문이 끝났을 때 stack 의 길이가 0보다 크면 쌍이 맞지 않은 것이므로 false 그렇지 않은 경우는 모든 케이스를 통과한 것이므로 true 를 리턴해주었다. 

 

 

두 번의 고비와 문제 해결과정

 

같은 문제를 두번이나 풀었는데도 오류를 잡는데 오랜 시간이 걸렸던 것 같다. 

첫 번째 고비는 top 을 변수로 선언해두고 top 을 사용하면서  pop을 하면 스택의 길이가 줄어드니 top 도 줄어들겠지 하는 멍청한 생각으로 인해 발생했다. 지금생각하니 웃음만 나온다 .정말 기초적인 부분이었는데 늘 이렇게 알고리즘 문제를 풀 때에는 기초적인 부분에서 실수를 해 시간낭비를 많이 하는 것 같다. 

두 번째 고비는 바보같은 생각으로 열린 괄호랑 닫힌 괄호를 각각의 stack 에 넣어 첫번째로 두 스택의 길이가 다를 때는 쌍이 안맞는 것이므로 false 를 반환하고 같이 pop 해서 쌍이 맞으면 되겠지 ? 했는데 ({}) 이렇게 들어온 순간 false 가 되어버린다.. 이것 또한 아주 멍청한 생각이었다 ... 

...

 

결국 해결해낸 방법으로는 맵을 사용해 key-value 로 묶고 top 변수는 for문안에 선언하여 계속해서 top 값이 바뀌게 해주었고 , 열린괄호만 stack 에 push 하고 닫힌 괄호가 나올 때 stack의 top 과 비교하여 문제를 해결하였다. 

 

오늘 스택 문제를 풀며 느낀 점은 개념만 안다고 해서 문제를 풀 수 있는 것은 아니다 ! 였다. 요즘 약간 코태기가 왔는지 공부가 너무 하기 싦었다. 그래서 알고리즘 문제도 안 풀고 놀았던 것 같다. 그래서 오늘 이런 시련을 겪은 것 같다 . 하지만 한편으로는 다시 공부를 열심히 해야겠다는 생각도 들었다. 이 마음 그대로 앞으로 남은 기간동안 치열하게 살아볼 것이다 .. !