2116. Check if a Parentheses String Can Be Valid

문제 링크


내 코드

해설 참고.


Solution

Approach 1: Stack

  • 8ms, 34.86MB
  • Complexity
    • Let nn be the size of the string s.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(n)O(n)
class Solution {
public:
    bool canBeValid(string s, string locked) {
        int length = s.size();
        // If length of string is odd, return false.
        if (length % 2 == 1) {
            return false;
        }

        stack<int> openBrackets, unlocked;

        // Iterate through the string to handle '(' and ')'
        for (int i = 0; i < length; i++) {
            if (locked[i] == '0') {
                unlocked.push(i);
            } else if (s[i] == '(') {
                openBrackets.push(i);
            } else if (s[i] == ')') {
                if (!openBrackets.empty()) {
                    openBrackets.pop();
                } else if (!unlocked.empty()) {
                    unlocked.pop();
                } else {
                    return false;
                }
            }
        }

        // Match remaining open brackets with unlocked characters
        while (!openBrackets.empty() && !unlocked.empty() &&
               openBrackets.top() < unlocked.top()) {
            openBrackets.pop();
            unlocked.pop();
        }

        if (!openBrackets.empty()) {
            return false;
        }

        return true;
    }
};

GPT (o3-mini-high)

이 코드는 주어진 문자열 s와 해당 인덱스별로 수정 가능한지 여부를 나타내는 locked 문자열을 이용하여,
현재 상태에서 괄호 문자열 s가 올바른 괄호 문자열(Valid Parentheses String)이 될 수 있는지 판단합니다.

올바른 괄호 문자열의 조건은 다음과 같습니다.

  • 문자열의 길이는 짝수여야 합니다.
  • 왼쪽부터 읽어갈 때, 어느 시점에서든 (의 개수가 )의 개수보다 적어서는 안 됩니다.
  • 최종적으로 (와 )의 개수가 동일해야 합니다.

문제의 특징:

  • locked[i] == '1'이면 해당 인덱스의 괄호는 변경할 수 없습니다.
  • locked[i] == '0'이면 해당 인덱스의 괄호는 ( 또는 )로 변경할 수 있습니다.

코드의 전체적인 아이디어는 두 개의 스택을 사용하여 진행됩니다.

코드 구성 및 동작 설명

1. 길이 검사

int length = s.size();
if (length % 2 == 1) {
    return false;
}
  • 목적:
    올바른 괄호 문자열은 항상 짝수 길이여야 합니다.
    길이가 홀수라면 어떤 변경을 해도 올바른 문자열을 만들 수 없으므로 바로 false를 반환합니다.

2. 두 개의 스택 선언

stack<int> openBrackets, unlocked;

  • openBrackets:
    잠긴 상태(locked[i]=='1')이고 '('인 인덱스들을 저장합니다.

  • unlocked:
    수정이 가능한 위치(locked[i]=='0')의 인덱스들을 저장합니다.
    이 위치의 괄호는 필요에 따라 ( 또는 )로 변경할 수 있습니다.

3. 문자열 순회하면서 괄호 처리

for (int i = 0; i < length; i++) {
    if (locked[i] == '0') {
        unlocked.push(i);
    } else if (s[i] == '(') {
        openBrackets.push(i);
    } else if (s[i] == ')') {
        if (!openBrackets.empty()) {
            openBrackets.pop();
        } else if (!unlocked.empty()) {
            unlocked.pop();
        } else {
            return false;
        }
    }
}

  • 수정 가능한 문자 처리 (locked[i]=='0'):

    • 인덱스 i를 unlocked 스택에 추가합니다.
      → 이 위치는 필요할 때 괄호 방향을 자유롭게 바꿀 수 있습니다.

  • 잠긴 괄호 처리 (locked[i]=='1'):

    • 만약 s[i]가 '('이면, 인덱스 i를 openBrackets 스택에 추가합니다.
    • 만약 s[i]가 ')'이면,
      1. 우선 openBrackets 스택에 여는 괄호가 있다면 매칭시켜서 스택에서 제거합니다.
        → 이는 현재 잠긴 닫는 괄호에 대해 대응하는 여는 괄호가 있음을 의미합니다.
      2. 만약 openBrackets가 비어있다면,
        • 수정 가능한 위치(unlocked)가 있다면 그 중 하나를 사용하여 괄호를 '('로 변경(또는 적절히 매칭)할 수 있으므로, unlocked 스택에서 하나 꺼냅니다.
      3. 만약 두 스택 모두 비어있다면,
        → 현재 닫는 괄호에 매칭할 수 있는 여는 괄호가 없으므로 올바른 괄호 문자열을 만들 수 없어서 false를 반환합니다.

4. 남은 여는 괄호와 수정 가능한 인덱스 매칭

while (!openBrackets.empty() && !unlocked.empty() &&
       openBrackets.top() < unlocked.top()) {
    openBrackets.pop();
    unlocked.pop();
}

  • 남은 openBrackets 처리:
    순회 후에도 openBrackets에 여는 괄호가 남아있다면,
    이 괄호들은 나중에 등장하는 수정 가능한 인덱스(unlocked)를 활용하여 ')'로 변경할 수 있어야 합니다.

  • 조건:

    • openBrackets.top() < unlocked.top() 조건은,
      현재 매칭하려는 여는 괄호의 인덱스가 수정 가능한 닫는 괄호로 변경할 수 있는 인덱스보다 앞에 있어야 함을 의미합니다.
      (괄호 매칭은 순서가 중요하기 때문입니다.)

  • 매칭이 가능하면 두 스택에서 해당 인덱스를 꺼냅니다.

5. 최종 판단

if (!openBrackets.empty()) {
    return false;
}

return true;

  • 남은 여는 괄호가 있다면:
    매칭되지 않은 여는 괄호가 남아있는 경우 올바른 괄호 문자열을 만들 수 없으므로 false를 반환합니다.

  • 모두 매칭되었다면:
    true를 반환합니다.

요약

  1. 문자열 길이가 홀수면 바로 false를 반환합니다.
  2. 문자열을 순회하면서,
    • 수정 가능한 인덱스는 unlocked 스택에 저장하고,
    • 잠긴 상태에서 '('는 openBrackets 스택에 저장합니다.
    • 잠긴 상태에서 ')'는 우선 openBrackets에서 매칭, 없으면 unlocked를 사용하여 매칭 시도합니다.
  3. 순회 후 남은 여는 괄호들은 나중에 등장하는 수정 가능한 인덱스를 활용하여 매칭시킵니다.
  4. 매칭되지 않은 여는 괄호가 남으면 false, 아니면 true를 반환합니다.

이와 같은 과정을 통해, 주어진 s가 수정 가능한 위치들을 적절히 활용하여 올바른 괄호 문자열로 만들 수 있는지를 판단합니다.


Approach 2: Constant Space

  • 7ms, 30.11MB
  • Complexity
    • Let nn be the size of the string s.
    • Time Complexity: O(n)O(n)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    bool canBeValid(string s, string locked) {
        int length = s.size();
        // If length of string is odd, return false.
        if (length % 2 == 1) {
            return false;
        }
        int openBrackets = 0, unlocked = 0;
        // Iterate through the string to handle '(' and ')'.
        for (int i = 0; i < length; i++) {
            if (locked[i] == '0') {
                unlocked++;
            } else if (s[i] == '(') {
                openBrackets++;
            } else if (s[i] == ')') {
                if (openBrackets > 0) {
                    openBrackets--;
                } else if (unlocked > 0) {
                    unlocked--;
                } else {
                    return false;
                }
            }
        }
        // Match remaining open brackets with unlocked characters.
        int balance = 0;
        for (int i = length - 1; i >= 0; i--) {
            if (locked[i] == '0') {
                balance--;
                unlocked--;
            } else if (s[i] == '(') {
                balance++;
                openBrackets--;
            } else if (s[i] == ')') {
                balance--;
            }
            if (balance > 0) {
                return false;
            }
        }

        if (openBrackets > 0) {
            return false;
        }

        return true;
    }
};

GPT (o3-mini-high)

아래 코드는 문자열 s와 해당 인덱스별로 수정 가능 여부를 나타내는 문자열 locked가 주어졌을 때,
잠긴 괄호들을 그대로 두고 수정 가능한 괄호들을 적절히 바꿔서 s를 올바른 괄호 문자열(Valid Parentheses String)로 만들 수 있는지를 판별하는 알고리즘입니다.

문자열을 올바른 괄호 문자열로 만들기 위한 기본 조건은 다음과 같습니다.

  • 전체 길이가 짝수여야 함
    (홀수 길이면 무조건 올바른 괄호 문자열이 될 수 없습니다.)

  • 왼쪽에서 오른쪽으로 읽을 때, 어느 순간이라도 닫는 괄호가 여는 괄호보다 많아서는 안 됩니다.
    (역방향에서도 동일하게 조건을 만족해야 합니다.)

이 문제에서 locked가 '1'인 인덱스는 고정되어 변경할 수 없고, '0'인 인덱스는 자유롭게 '('나 ')'로 바꿀 수 있습니다.

코드는 두 번의 순회를 진행합니다.
첫 번째 순회는 왼쪽→오른쪽으로 진행하여 앞쪽에서의 괄호 매칭 가능성을 확인하고,
두 번째 순회는 오른쪽→왼쪽으로 진행하여 뒤쪽에서의 괄호 매칭 가능성을 확인합니다.

1. 초기 검사

int length = s.size();
if (length % 2 == 1) {
    return false;
}
  • 설명:
    올바른 괄호 문자열은 항상 짝수 길이여야 합니다.
    길이가 홀수이면 무조건 올바른 문자열을 만들 수 없으므로 false를 반환합니다.

2. 왼쪽 → 오른쪽 순회

int openBrackets = 0, unlocked = 0;
for (int i = 0; i < length; i++) {
    if (locked[i] == '0') {
        unlocked++;
    } else if (s[i] == '(') {
        openBrackets++;
    } else if (s[i] == ')') {
        if (openBrackets > 0) {
            openBrackets--;
        } else if (unlocked > 0) {
            unlocked--;
        } else {
            return false;
        }
    }
}

  • 변수 설명:

    • openBrackets: 잠긴(locked) 상태에서 등장한 여는 괄호 '('의 개수를 카운트합니다.
    • unlocked: 수정 가능한(locked가 '0') 인덱스의 개수를 누적합니다.

  • 순회 동작:

    1. 수정 가능한 인덱스
      • locked[i] == '0'인 경우, 해당 위치는 나중에 필요에 따라 '(' 또는 ')'로 바꿀 수 있으므로
        unlocked 카운트를 증가시킵니다.
    2. 잠긴 여는 괄호
      • locked[i]=='1'이고 s[i]=='('이면, openBrackets를 증가시킵니다.
    3. 잠긴 닫는 괄호
      • locked[i]=='1'이고 s[i]==')'인 경우,
        • 우선: 이미 만난 잠긴 여는 괄호(openBrackets)가 있다면 매칭시키기 위해 하나 감소시킵니다.
        • 없다면: 수정 가능한 인덱스(unlocked)가 있다면 그 위치를 활용해 괄호를 '('로 바꿔 매칭할 수 있으므로 unlocked를 감소시킵니다.
        • 만약 둘 다 없다면: 매칭할 수 없으므로 false를 반환합니다.

요약:
왼쪽→오른쪽 순회에서는 닫는 괄호를 만났을 때 현재까지 확보한 잠긴 여는 괄호나 수정 가능한 인덱스를 사용하여 대응할 수 있는지 검사합니다.

3. 오른쪽 → 왼쪽 순회

int balance = 0;
for (int i = length - 1; i >= 0; i--) {
    if (locked[i] == '0') {
        balance--;
        unlocked--;
    } else if (s[i] == '(') {
        balance++;
        openBrackets--;
    } else if (s[i] == ')') {
        balance--;
    }
    if (balance > 0) {
        return false;
    }
}

  • 목적:
    오른쪽에서 왼쪽으로 진행하면서, 뒤쪽에 남아 있을 수 있는 여는 괄호들을 적절히 닫을 수 있는지 확인합니다.
    (역순으로 읽으면 여는 괄호는 닫아줘야 할 대상으로, 닫는 괄호는 매칭된 것으로 간주할 수 있습니다.)

  • 변수 설명:

    • balance: 현재 오른쪽→왼쪽 순회에서의 “불균형” 정도를 나타냅니다.
      • 닫는 괄호는 balance를 감소시키고, 여는 괄호는 balance를 증가시킵니다.

  • 순회 동작:

    1. 수정 가능한 인덱스 (locked[i]=='0')
      • 이 경우, 해당 위치를 ')'로 바꿀 수 있다고 가정하여 balance를 감소시킵니다.
      • 동시에 사용한 수정 가능 인덱스이므로 unlocked를 감소시킵니다.
    2. 잠긴 여는 괄호
      • s[i]=='('인 경우, 뒤에서 보면 여는 괄호는 닫혀야 할 대상으로 작용하므로 balance를 증가시키고,
        이미 사용했던 여는 괄호 수인 openBrackets를 감소시킵니다.
    3. 잠긴 닫는 괄호
      • s[i]==')'인 경우, balance를 감소시킵니다.
    4. 즉시 검증
      • 만약 순회 중 balance가 양수가 되면, 이는 오른쪽에서 봤을 때 여는 괄호가 닫는 괄호보다 많다는 뜻이므로
        유효한 매칭이 불가능하여 false를 반환합니다.

요약:
오른쪽→왼쪽 순회에서는, 수정 가능한 인덱스를 적절히 활용하여 뒤쪽의 여는 괄호들이 올바르게 닫힐 수 있는지 확인합니다.
만약 어느 시점에서라도 매칭이 불가능하면 false를 반환합니다.

4. 최종 검증

if (openBrackets > 0) {
    return false;
}
return true;
  • 설명:
    두 번의 순회 후에도 남은 잠긴 여는 괄호(openBrackets)가 있다면 매칭되지 않은 괄호가 남은 것이므로 올바른 문자열을 만들 수 없습니다.
    그렇지 않으면 모든 괄호를 올바르게 매칭할 수 있으므로 true를 반환합니다.

결론

이 알고리즘은

  • 왼쪽→오른쪽 순회로 닫는 괄호를 만났을 때 매칭할 여는 괄호(또는 수정 가능한 인덱스)가 충분한지 확인하고,
  • 오른쪽→왼쪽 순회로 남은 여는 괄호들이 뒤쪽에서 닫힘 처리될 수 있는지 확인합니다.

두 방향 모두에서 올바른 괄호 매칭이 가능하다면, 수정 가능한 인덱스들을 적절히 활용하여 s를 올바른 괄호 문자열로 만들 수 있으므로 true를 반환합니다.
그렇지 않으면 false를 반환합니다.