[알고리즘] 괄호쌍 문제

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

 

입력: string 타입의 문자열

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

 

🔽 입출력 예시

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

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

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

 

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

 

	const balancedBrackets = function (str) {
	const stack = [];
	for (let i = 0; i < str.length; i++) {
	const top = stack[stack.length - 1];
	switch (str[i]) {
	case "[":
	stack.push(str[i]);
	break;
	case "(":
	stack.push(str[i]);
	break;
	case "{":
	stack.push(str[i]);
	break;
	case "]":
	if (top === "[") stack.pop();
	else if (!stack.length) return false;
	break;
	case ")":
	if (top === "(") stack.pop();
	else if (!stack.length) return false;
	break;
	case "}":
	if (top === "{") stack.pop();
	else if (!stack.length) return false;
	break;
	}
	}
	if (stack.length) return false;
	else return true;
	};

view raw algorithm-brackets hosted with ❤ by GitHub

 

 

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 쌍으로 데이터를 표현할 수 있는 객체로 변수를 하나 만들어주면 되는 거였다. 

 

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

 

	const balancedBrackets = function (str) {
	const stack = [];
	const open = {
	"[": "]",
	"(": ")",
	"{": "}",
	};
	const close = "])}";
	for (let i = 0; i < str.length; i++) {
	if (str[i] in open) {
	stack.push(str[i]);
	} else if (close.includes(str[i])) {
	// stack의 top이 닫힌 괄호의 짝인 열린 괄호인 경우
	const top = stack[stack.length - 1];
	if (open[top] === str[i]) {
	stack.pop();
	}
	}
	}
	return !stack.length;
	};

view raw balancedBrackets-revu hosted with ❤ by GitHub

 

 

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

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. 모든 경우를 빠뜨리지 않고 커버할 수 있는 분기 설정을 고민해야 한다.