코딩테스트 문제 복습 (Valid Parentheses)

 

스택과 시간복잡도를 사용하는 문제

문제:

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

(출처: https://leetcode.com/problems/valid-parentheses/description/)

문제는 문자 '()', '()', '{), '}', '[]', '[]'만 포함된 문자열이 주어지면 입력 문자열이 유효한지 확인하는 문제이다.

 

조건은 다음과 같다.

• 열린 괄호는 동일한 유형의 괄호로 닫아야 한다.
• 열린 괄호는 올바른 순서로 닫아야 한다.
• 모든 근접 브래킷에는 동일한 유형의 열린 브래킷이 있다.

그래서 답이 "()[]{}" 식으로 나오면 true, "(]"나 "({[}])" 식으로 나오면 false가 나와야 한다.

 

이 문제는 스택과 시간복잡도 개념이 응용되는데, 각각의 개념은 다음과 같다.

• 스택: 가장 나중에 들어간 데이터가 가장 먼저 나오는 후입선출(LIFO) 방식의 구조
• 시간복잡도: 알고리즘의 효율성을 평가하는 지표 중 하나로, 입력크기에 따라 알고리즘이 얼마나 빠르게 실행되는지를 나타내는 지표

이 문제에서는 문자열 길이만큼 한번 순회하면서 시간복잡도는 O(n)으로 유지하며, 특정 문자열에 포함된 괄호의 한쪽면과 다른쪽면이 서로 맞아 떨어질 때 true를 반환하면 된다.

 

열린 괄호가 닫힌 괄호와 순서대로 맞아야 한다는 것은 가장 나중에 열린 괄호가 가장 먼저 닫혀야 한다는 뜻이 된다. 이는 전형적인 LIFO 구조이다.

 

그래서 라이브 코딩테스트 때는 어떻게 풀어야할지 갈피를 못잡다가 결과도 안나오는 이상한 코드로 제출했는데, 다시 풀었을 때는 아래와 같이 풀었다.

 

([{}])라는 순서로 나온다면

• "(" → 스택에 push
• "[" → 스택에 push
• "{" → 스택에 push
• "}" → { 와 짝이 맞는지 확인하고 pop
• "]" → [ 와 맞는지 확인하고 pop
• ")" → ( 와 맞는지 확인하고 pop

중간에 짝이 안맞으면 거기서 false를 반환하고, 모두 잘 맞아서 빈 배열이 되면 true를 반환하도록 했다.

 

그래서 최종적으로 나온 코드는 다음과 같다.

const bracketValid = (string) => {
  const stack = [];
  const bracketMapping = {
    "(" : ")",
    "[" : "]",
    "{" : "}",
  }
  
  for (let char of string) {
    if (["(", "[", "{"].includes(char)) {
      // 열린 괄호일 때는 stack에 push
      stack.push(char);
    } else {
      // 닫힌 괄호일 때는 가장 마지막에 넣은 열린 괄호와 비교해서 쌍이 맞는지 확인하고 pop
      if (stack.pop() !== bracketMapping[char]) {
        return false;
      }
    }
  }
  
  return stack.length === 0; // 남은 괄호가 없으면 true
}