LeetCode - Minimum Remove to Make Valid Parentheses

문제 설명

(,),소문자로 이루어진 문자열이 주어진다.
니가 할 일은, 소괄호의 짝을 맞추는 것이다.

또한 문자열은 다음과 같은 규칙을 이루어야 하는데

• 빈 문자열이거나 소문자만 이루어질 것
• AB (A는 올바른 문자열, B도 올바른 문자열 둘이 Concat된 것)
• 혹은 (A) (소괄호속에 같힌 올바른 문자열)

로 이루어져 있어야 할 것이다.

규칙자체를 문제에 제시 해놨기 때문에, 그대로 규칙을 문자열에 대입하면 된다.

해결 방법

괄호 문제가 나오면 대부분 스택을 이용한다.
이번에는 조금 특이한게 있다면 기존의 문자열과 valid과 통과된 소괄호의 규칙을 지키면서 이뤄나가는 것이었다.

따라서 남는 ( 에 대해서 따로 처리해줄 필요가 있는데,
남는 ( 의 경우는 뒤에서 부터 Index 값을 찾아 제거 해주면 해결 되는 간단한 문제다

코드

import java.util.*;

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        StringBuilder stringBuilder = new StringBuilder("");
        
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            try{
                if(c=='('){
                    stack.push('(');
                    stringBuilder.append(c);
                }else if(c==')'&&stack.peek()=='('){
                    stack.pop();
                    stringBuilder.append(c);
                }else
                    stringBuilder.append(c);
            }catch(Exception e){}
        }
            
        while(!stack.isEmpty()){
            int index = stringBuilder.lastIndexOf("(");
            if(index!=-1)
                stringBuilder.deleteCharAt(index);
            stack.pop();
        }
    
        return stringBuilder.toString();
    }
    
}

소감

중간에 보면 코드 고치기 귀찮아서 try catch로 감싸버린 부분이 있다.
뭐 상관없다고 생각한다.

또한 stack에 (가 남을경우 뒤에서부터 index를 찾아 삭제한다.

또한 StringBuilder를 사용한 이유는, 아무래도 문자열을 도중에 수정하는 경우가 많다보니까
mutable한 객체인 StringBuilder를 써서 최적화를 하려 했다.

푸는데는 한 10분 정도 걸린듯?

결과