LeetCode 678 - Valid Parenthesis String (Medium)

문제

LeetCode - 678번

풀이 과정

주어진 문자열에서 괄호쌍이 올바르게 짝지어졌는지 판단하는 문제입니다.

다만 이 문제에서는 와일드카드(*) 가 존재하여 약간의 다른 방식의 접근이 필요합니다.

우선 이 와일드카드를 어떤 식으로 처리할지 결정해야합니다.

각각의 와일드 카드는 ( 혹은 ) 혹은 빈칸 으로 사용될 수 있으므로
현재 괄호 스택을 가지고는 어떤 방식으로 사용해야할지 알 수 없습니다.

따라서 해당 와일드 카드는 다음 세 가지 경우로 사용 방법을 나눌 수 있습니다.

 

• * 보다 앞서 발견된 ( 문자의 ) 역할
• * 보다 늦게 발견된 ) 문자의 ( 역할
• 아무 역할도 하지 않는 빈칸

 

다시 말해 ) 문자에 대응되는 ( 가 이전에 스택에 존재하지 않을 경우 * 를 대신 사용하도록 하면 됩니다.
따라서 큐 에 * 문자가 발견된 순서로 집어넣고 활용하도록 하였습니다.

( 문자의 경우 모든 문자를 순회한 뒤 스택에 남아있는 것이 있다면 * 문자로 ) 역할을 할 수 있는지 판단합니다.
이 경우 * 문자가 스택에 존재하는 ( 보다 나중에 발견되어야 하므로 인덱스를 비교하여 결정하도록 하였습니다.

코드

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function (s) {
  const stack = [];
  const asterisk = [];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);
    } else if (s[i] === ")") {
      if (stack.length) {
        stack.pop();
      } else {
        if (asterisk.length) {
          asterisk.shift();
        } else {
          return false;
        }
      }
    } else {
      asterisk.push(i);
    }
  }

  // '(' 가 스택에 남아있는 경우 와일드 카드 사용 가능성 판단
  for (let i = asterisk.length; i > 0; i--) {
    if (!stack.length) {
      return true;
    }
    if (asterisk[asterisk.length - 1] > stack[stack.length - 1]) {
      stack.pop();
    }
    asterisk.pop();
  }

  return stack.length === 0;
};

const input = "(())((())()()(*)(*()(())())())()()((()())((()))(*";
console.log(checkValidString(input));