[LeetCode] 2116. Check if a Parentheses String Can Be Valid

https://leetcode.com/problems/check-if-a-parentheses-string-can-be-valid/description/

leetcode - Check if a Parentheses String Can Be Valid

문제 유형: 문자열 처리, 2-pass

문제 난이도: Medium

 

문제

A parentheses string is a nonempty string consisting only of '(' and ')'. It is valid if any of the following conditions is true:

• It is ().
  It can be written as AB (A concatenated with B), where A and B are valid parentheses strings.
  It can be written as (A), where A is a valid parentheses string.
• You are given a parentheses string s and a string locked, both of length n. locked is a binary string consisting only of '0's and '1's. For each index i of locked,
• If locked[i] is '1', you cannot change s[i].
  But if locked[i] is '0', you can change s[i] to either '(' or ')'.

Return true if you can make s a valid parentheses string. Otherwise, return false.

 

'('또는 ')'로만 주어진 괄호문자열 s가 주어집니다. 비트문자열 locked가 주어집니다.

locked[i]가 '1'이라면 괄호를 반대로 바꿀 수 없습니다. '0'이라면 가능합니다.

괄호를 가능한 마음대로 바꿔서 유효한 괄호쌍을 만들 수 있다면 true, 아니면 false를 반환하시오.

 

풀이

두 번의 순회로 풀 수 있다.

가변의 괄호의 개수 var,

고정된 여는괄호 op,

고정된 닫는괄호 ch가 있다고 하자.

개수를 순차적으로 세주면서, 만약 닫는괄호의 수가 가변괄호 + 여는괄호의 개수보다 크다면 유효하지 않다.

또한, 다 돌고나서 여는 괄호가 닫는괄호와 가변괄호의 개수보다 크다면 유효하지 않다.

 

반대로도 똑같이 해준다.

 

마지막까지 false가 아니면 true이다.

 

코드

C++

class Solution {
public:
    bool canBeValid(string s, string locked) {
        int n = s.size();
        if(n%2 == 1) return false;

        int var = 0;
        int op = 0;
        int cl = 0;
        for(int i = 0; i < n; ++i) {
            if(locked[i] == '0') var++;
            else if(s[i] == '(') op++;
            else cl++;

            if(cl > var + op) return false;
        }
        if(op > var + cl) return false;

        var = 0;
        op = 0;
        cl = 0;
        for(int i = n-1; i >= 0; --i) {
            if(locked[i] == '0') var++;
            else if(s[i] == ')') op++;
            else cl++;

            if(cl > var + op) return false;
        }
        if(op > var + cl) return false;

        return true;
    }
};