LeetCode (C/C++) 678. Valid Parenthesis String

https://leetcode.com/problems/valid-parenthesis-string/submissions/

---

풀이

'('의 개수에 따라 *을 다르게 해석하려고 했으나 *의 위치 처리를 어떻게 해야 하는지 몰라서 막혔었다. 해당 알고리즘으로는 컨테이너에 '('과 '*'의 위치를 저장하고 이를 비교하면 됐었다.

 

 

하지만 더 좋은 풀이를 찾아서 해당 방법으로 풀었다.

해당 풀이는 열린 괄호 개수의 최대(cmax)/최소(cmin) 값을 이용한 풀이로, 괄호가 나올 때마다 cmin/cmax 값을 조정했다.

이 때 '*'은 어떤 식으로 쓸지 모르니 cmax++ (열린 괄호로 쓸 경우) / cmin-- (닫힌 괄호로 쓸 경우) 를 모두 고려했다.

 

매 탐색마다 cmax < 0 이라면 열린 괄호 개수 < 닫힌 괄호 개수 이므로 에러 처리를 해줬고,

*을 닫힌 괄호로 쓸 경우 cmin의 값은 음수가 될 수 있으므로 해당 값을 조정해주었다.

 

자세한 방법은 아래 링크를 참고하면 좋을 듯 하다.

https://leetcode.com/problems/valid-parenthesis-string/discuss/543521/Java-Count-Open-Parenthesis-O(n)-time-O(1)-space-Picture-Explain

---

코드 

class Solution {
public:
    bool checkValidString(string s) {
        int cmin = 0, cmax = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                cmin++;
                cmax++;
            }
            
            else if (s[i] == ')') {
                cmin--;
                cmax--;
            }
            
            else {
                cmax++; // *을 열린 괄호로 사용
                cmin--; // *을 닫는 괄호로 사용
            }   
            if (cmax < 0) return false; // cnt_open < cnt_close
            cmin = max(cmin, 0); // *을 빈문자열 처리
        }
        if (cmin > 0) return false;
        return cmin == 0;
    }
};

 

코드 - 틀린 풀이 (고칠 예정)

class Solution {
public:
    bool checkValidString(string s) {
        int cnt = 0, cntStar = 0;
        for (int i = 0; i < s.size(); i++) {
            
            if (s[i] == '(')
                cnt++;
            
            else if (s[i] == ')') {
                
                printf("cnt : %d star : %d\n", cnt, cntStar);
                
                if (cnt <= 0) {
                    if (cntStar > 0)
                        cntStar--;
                    else 
                        return false;
                }
                else
                    cnt--;
            }
            else cntStar++;
        }
        if (cnt == 0 || cnt <= cntStar)
            return true;
        return false;
    }
};