1249. Minimum Remove to Make Valid Parentheses

💡 풀이

var minRemoveToMakeValid = function (s) {
  let stack = [];
  let answer = [...s];

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') stack.push(i);
    else if (s[i] === ')') {
      stack.length ? stack.pop() : (answer[i] = '');
    }
  }
  if (stack.length > 0) {
    while (stack.length) answer[stack.pop()] = '';
  }

  // console.log('답: ', answer.join(''));
  return answer.join('');
};

s = '))((';
minRemoveToMakeValid(s);

📝 정리

stack과 관련한 문제다. 무의식적으로 괄호가 있는 문제만 보면 stack으로 생각하게 되는 습관이 들어버렸다..하하.. 시간 복잡도 O(N), 공간 복잡도 O(N)으로 문제를 해결하였다.

• 먼저, stack 배열을 선언해주고 답이 될answer = [...s](=s.split('')) 배열을 선언해 준다.

• 문자열 s에서는 괄호만 확인하면 된다. (일 때는 stack에 해당 index를 넣어준다.

• )일 때는 stack에 요소가 들어있다면 stack.pop()을 통해 꼭대기의 요소를 지워주고, 없다면 inValid한 괄호 모양이 되는 것이니 해당 부분 인덱스의 요소를 ''(=없음)으로 만들어준다.

• 추가적으로 s = '))((' 인 경우에, 마지막 while문이 없다면 answer='(('가 된다.(문제의 예시대로라면 ''가 답이 되어야 함.)

• 따라서 만약 stack에 요소가 남아있다면 answer 배열에서 stack.pop()에 해당하는 인덱스의 요소를 ''(=없애기)로 만들어준다.

• 마지막으로 answer 배열을 join('')을 통해 문자열로 만들어주면 답이 나온다.

수정, 지적을 환영합니다!

문제 링크

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

LeetCode GitHub

https://github.com/tTab1204/LeetCode