최소 추방으로 유효한 괄호 만들기

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/

로직 분석

// 문자열을 좌에서 우로 탐색한다
// 문자열을 탐색하면서 마주칠 수 있는 경우의 수는 "(" 와 "a-z" 와 ")" 일 것이다

// 이 문제에서 추적해야하는 것은 '몇 개의 좌괄호가 짝이 없는지'이다

case1) 좌괄호를 먼저 마주칠 경우
// 좌괄호를 마주치면 해당 좌괄호의 인덱스를 스택에 담는다.
// 우괄호를 마주치면 스택에서 좌괄호를 pop한다.
// 끝까지 다 검문을 마친 후 스택을 확인해서 해당 인덱스에 위치한 좌괄호를 추방한다.

case2) 우괄호를 먼저 마주칠 경우
// 하지만 좌괄호보다 우괄호를 먼저 마주칠 수도 있다. 때문에 스택에 들어온 좌괄호가(짝) 있는지 확인해야한다.
// 스택에 담긴 좌괄호가 없다면 우괄호는 짝이 없는 것이므로 우괄호를 즉시 공백으로 변환한다

내 코드

function solution(s) {
  let stack = [];
  let answer;
  split_s = s.split("");
  for (i = 0; i < s.length; i++) {
    let p = 0;
    if (split_s[p] === ")") {
      if (stack.length === 0) {
        split_s.slice(split_s[p], split_s[p + 1]);
      } else stack.pop();
    }
    if (split_s[p] === "(") {
      stack.push(split_s[p].indexOf());
    } 
    else p++;
  }
  for (i = 0; i < stack.length; i++) {
    if (stack.length !== 0) {
      let count = 0;
      split_s.slice(split_s[stack[i - count]], split_s[stack[i + 1 - count]]);
      count++;
    }
  }
  let res_s = split_s.join("");

  return (answer = res_s);
}

let s = "a)bc(d)";
console.log(solution(s));

솔루션

const string1 = "(ab(cd)";

const minRemoveToMakeValid = function (str) {
  const res = str.split("");
  const stack = [];

  for (let i = 0; i < res.length; i++) {
    if (res[i] === "(") {
      stack.push(i);
    } else if (res[i] === ")" && stack.length) {
      stack.pop();
    } else if (res[i] === ")") {
      res[i] = "";
    }
  }

  while (stack.length) {
    const deleteIdx = stack.pop();
    res[deleteIdx] = "";
  }

  return res.join("");
};

console.log(minRemoveToMakeValid(string1));

slice로 덜어낼 경우 index가 배열의 인덱스가 한 칸씩 당겨지기 때문에 문제가 복잡해진다. 때문에 인덱스가 당겨지지 않게 우괄호를 공백('')으로 할당해주는 것이 포인트이다.