💡 풀이
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/
