[알고리즘] 괄호쌍 문제

워낙 유명한 문제라 간략하게 입출력만 써보자면,

 

입력: string 타입의 문자열

출력: 입력의 문자열 내의 모든 괄호가 짝이 맞는지 여부에 대한 boolean 타입 

 

🔽 입출력 예시

let output = balancedBrackets('[](){}');
console.log(output); // --> true

output = balancedBrackets('[({})]');
console.log(output); // --> true

let output3 = balancedBrackets('[(]{)}');
console.log(output3); // --> false

 

🔽 첫번째 문제 풀이 - switch 문으로 개별 케이스 나눔

 

 

 

switch 문으로 써서 풀긴 했는데, 사실 위의 3가지 경우는 여는 괄호로 실행해야 하는 코드가 동일하고, 아래 3가지 경우는 닫는 괄호로 마찬가지로 동일한 코드라 중복이 있다. 이걸 처음에는 여는 괄호/닫는 괄호로 다음과 같이 변수 선언을 먼저 해준 다음에 if-else 문으로 나눠서 두 가지 경우로 해결하고 싶었다. 그런데 닫는 괄호의 경우 각 괄호에 맞는 짝을 써줘야 해서 이 부분을 해결하지 못해서 차라리 중복이 좀 있더라도 한 눈에 잘 보이는 switch 문으로 코드를 바꿔서 문제를 풀었다. 

 

const open = '[({';
const close = '])}';

if (open.includes(str[i])) {
    stack.push(str[i]);
} else if (close.includes(str[i])) {
    // stack의 top이 닫힌 괄호의 짝인 열린 괄호인 경우
    stack.pop();
}

 

그런데 레퍼런스 코드를 보니 짝, 쌍이라는 걸 표현할 수 있는 방법이 있다. key-value 쌍으로 데이터를 표현할 수 있는 객체로 변수를 하나 만들어주면 되는 거였다. 

 

🔽 수정한 문제 풀이 - 객체에 여는 괄호-닫는 괄호 쌍을 만들어 줌

 

 

 

이렇게 코드를 작성하면 기본적인 테스트를 통과하는데, 아래와 같이 입력값에 여는 괄호 없이 닫는 괄호만 들어오는 경우가 처리가 안 된다. 

balancedBrackets(')')

사실 첫 번째 풀이 때도 이 부분에 대한 고려가 안 되어서 있어서 닫는 괄호의 경우 18, 22, 26번 줄에 위의 edge case 처리를 위한 코드 else if (!stack.length) return false; 를 따로 적어줬다. 두번째 문제 풀이에서도 닫힌 괄호가 들어오는 경우, for loop 안의 코드를 다음과 같이 else 문을 한 줄 더 작성해 주면 모든 케이스가 통과되긴 한다. 

 

    const top = stack[stack.length - 1];

    if (str[i] in open) {
      stack.push(str[i]);
    } else if (close.includes(str[i])) {
      if (open[top] === str[i]) {
        stack.pop();
      } else return false; // 추가된 부분
    }

 

이런 edge case 방어를 위한 코드 없이 처음부터 모든 경우가 다 고려되는 코드를 짜는 것이 가장 좋을 텐데, 이렇게 모든 경우를 커버할 수 있는 분기 설정이나 코드 처리가 아직 어렵다. 

 

마지막 최종 return 값도 첫번째 문제 풀이에서는 if - else 로 나눠서 처리해줬는데 return !stack.length; 라는 한 줄로 처리해줄 수 있는 거였다. 오늘 graph 구현 문제를 풀면서 이와 비슷한 return 값 처리 방법을 하나 더 알게 됐는데, 아래와 같이 this.matrix[vertex] 값이 있으면 true를 리턴하고, 같이 없으면 false를 리턴하는 contains() 메소드를 짤 때였다. 

 contains(vertex) {
    if (this.matrix[vertex]) return true;
    else return false;
  }

 

레퍼런스 코드를 보니 이것도 not 연산자를 두 번 연달아 써서 바로 return 시켜버릴 수 있었다. 

 contains(vertex) {
    return !!this.matrix[vertex];
  }

 

이런걸 syntactic sugar 라고 부르는 걸지도 모르겠지만, 가독성을 해치지 않는 선에서는 코드 타이핑은 적게 할 수록 좋으니까... 😇

 

💡 배운 점 세 줄 요약: 
1. 여는 괄호-닫는 괄호처럼 데이터가 연관성을 가질 때, key-value 쌍으로 저장할 수 있다. 
2. if - else 분기로 boolean 값을 리턴하는 경우 ! 연산자 또는 !! 연산자를 이용해 바로 리턴할 수 있다. 
3. 모든 경우를 빠뜨리지 않고 커버할 수 있는 분기 설정을 고민해야 한다.