[leetcode] Minimum Remove to Make Valid Parentheses

문제

• 문제 링크
• '(', ')'와 영어 소문자로 이루어진 문자열 s가 주어진다. '(' 또는 ')'를 최소한으로 지워서 괄호가 제대로 닫혀있는 문자열을 반환해야 한다.
• 제약 조건
  • 문자열 길이: 1 <= s.length <= 10^5

풀이

풀기 전

• 처음에 잘못 생각해서 '그냥 열고 닫는 괄호 개수 각각 센 다음 적은 괄호 빼주면 되지 않나' 했는데 닫는 괄호가 먼저 나오는 경우를 생각하지 않은 거였다.
• 스택을 써서 풀어보기로 했다. 문자열을 순회하면서, 여는 괄호('(')는 스택에 담고 닫는 괄호(')')를 만났을 땐 스택을 체크하면 된다.
  • 여는 괄호('(')를 만났을 때 스택에 넣는다.
  • 닫는 괄호(')')를 만났을 때
    1. 스택이 비어있다면 대응되는 '('가 없다는 의미이다. 지금 만난 ')'는 제거해야 한다.
    2. 스택이 비어있지 않다면 대응되는 '('가 있다는 의미이다. 스택에서 대응되는 '('를 하나 빼준다.
  • 순회가 끝났을 때 스택이 비어있지 않다면, '('에 대응되는 ')'가 없다는 뜻이다. 스택에 남아있는 '('를 제거해야 한다. 스택에 인덱스를 담게 해서 '('에 접근 후 제거하도록 했다.

코드

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Integer> stack = new Stack<>();
        char[] chars = s.toCharArray();
        
        for (int i=0; i<chars.length; i++) {
            if (chars[i] == '(') {  // 여는 괄호 만나면 스택에 넣는다. 나중에 참조하기 쉽도록 인덱스로 넣었다.
                stack.add(i);
            } else if (chars[i] == ')') {  // 닫는 괄호 만나면 스택 체크한다.
                if (stack.isEmpty())  // 스택이 비어있으면 대응되는 여는 괄호가 없다는 거다.
                    chars[i] = '*';
                else  // 대응되는 여는 괄호가 있으면 스택에서 빼준다.
                    stack.pop();
            }
        }
        while (!stack.isEmpty())  // 스택이 비어있지 않다면 짝이 없는 여는 괄호가 있다는 거다. 제거 대상이다.
            chars[stack.pop()] = '*';

		// 제거 대상은 '*'로 수정해줬다. '*'을 제외한 문자열을 반환해준다.
        StringBuilder sb = new StringBuilder();
        for (char ch : chars) {
            if (ch == '*')
                continue;
                
            sb.append(ch);
        }
        return sb.toString();
    }
}

푼 후

• 지난 문제에서 스택을 써서 그런지 이번 문제에선 스택을 쉽게 떠올려서 사용했다.
• 문자열을 두번만 순회하기 때문에 시간 복잡도는 O(s.length)이다. 스택에는 최대 문자열만큼만 들어갈 수 있기 때문에 공간 복잡도도 O(s.length)이다.