[LeetCode] 1249. Minimum Remove to Make Valid Parentheses

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

Leetcode - Minimum Remove to Make Valid Parentheses

문제 유형 : 문자열 처리 / 스택

문제 난이도 : Medium

 

문제

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or
• It can be written as AB (A concatenated with B), where A and B are valid strings, or
• It can be written as (A), where A is a valid string.

문자열 s가 주어진다. 소괄호 '(', ')'와 영문 소문자로 구성되어있다.

최소 개수의 괄호를 지워서 유효한 문자열로 만들어야 합니다. 유사답안이 인정됩니다.

 

유효한 문자열의 조건은 다음중 하나이상 만족하면 됩니다:

• 빈 문자열 또는 한 글자의 영소문자
• 또는 접합된 유효한 문자열
• 유효한 문자열의 양쪽을 괄호로 감싼 꼴

 

풀이

스택을 사용하는 방법과, 사용하지 않는 방법이 있다.

어쨌든, 핵심은 유효하지 않은 괄호를 제거하는 것인데,

만약 앞의 여는 괄호보다 초과되는 닫는 괄호가 나오면, 그 괄호는 없애야 한다.

만약 앞의 닫는 괄호보다 초과되는 여는 괄호가 나오면, 그 괄호는 없애야 한다.

 

문자열을 순차적으로 순회하면서, 여는 괄호를 초과하는 닫는 괄호를 제외시킨다.

반대로 순회하면서, 닫는 괄호를 초과하는 여는 괄호를 제외시킨다.

이 과정에서 임시 문자열을 새로 만들거나, 스택을 이용하면, 문자열이 뒤집어진 상태일것이다.

이를 뒤집어서 반환하면 된다.

 

코드

C++ - 스택을 이용한 풀이

class Solution {
public:
    string minRemoveToMakeValid(string s) {
        stack<int> st;
        int opening = 0;
        int closing = 0;
        string res = "";

        for(const char ch : s) {
            if(ch == '(') opening++;
            else if(ch == ')') closing++;

            if(closing > opening) {
                closing--;
                continue;
            }

            st.push(ch);
        }

        while(!st.empty()) {
            auto ch = st.top();
            st.pop();

            if(ch == '(' && opening > closing) opening--;
            else res += ch;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};

 

Go - 스택을 이용하지 않은 풀이

func minRemoveToMakeValid(s string) string {
	var temp strings.Builder
	var opening int

	for _, ch := range s {
		if ch == '(' {
			opening++
		} else if ch == ')' {
			if opening > 0 {
				opening--
			} else {
				continue
			}
		}
		temp.WriteRune(ch)
	}
	s = ""
	opening = 0

	for i := temp.Len() - 1; i >= 0; i-- {
		ch := temp.String()[i]
		if ch == ')' {
			opening++
		} else if ch == '(' {
			if opening > 0 {
				opening--
			} else {
				continue
			}
		}

		s += string(ch)
	}

	return reverseString(s)
}

func reverseString(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}