(Python3) - LeetCode (Medium) : 1400. Construct K Palindrome Strings

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

구현 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

다음 변수를 선언해줍니다.

• 최소 개수(low): 가능한 최소 ( 개수
• 최대 개수(high): 가능한 최대 ( 개수

📔 풀이과정

 

• s의 길이가 홀수라면 괄호짝이 맞지 않으므로 False를 반환합니다.
• 왼쪽에서 오른쪽 (left-to-right) for loop로 스캔해줍니다.
  
  • locked[i] == '0' 이면 s[i]를 ( 또는 )로 변경 가능합니다.
  • low가 음수가 되면 유효하지 않은 문자열이므로 False 반환합니다.
  • high가 음수가 되면 더 이상 균형을 맞출 수 없으므로 False 반환합니다.
• 오른쪽에서 왼쪽 (right-to-left) 스캔해줍니다.
  • low, high 역할이 반대로 적용됩니다.
  • 위와 동일한 로직을 사용하여 검증합니다.
• 시간 복잡도 O(n)
  • n개의 배열을 두 번 순회하기 때문입니다.

 

📔 정답 출력 | 반환

True를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
  def canBeValid(self, s: str, locked: str) -> bool:
    n = len(s)
    if n % 2 == 1:
      return False

    low, high = 0, 0

    # 왼쪽에서 오른쪽으로 확인
    for i in range(n):
      if locked[i] == '1':  # 변경 불가능
        if s[i] == '(':
          low += 1
          high += 1
        else:
          low -= 1
          high -= 1
      else:  # 변경 가능
        low -= 1  # 최악의 경우 모두 ')'로 취급
        high += 1  # 최선의 경우 모두 '('로 취급

      if high < 0:  # ')'가 너무 많아서 균형 불가능
        return False
      low = max(low, 0)  # low는 음수가 되지 않도록 보정

    low, high = 0, 0

    # 오른쪽에서 왼쪽으로 확인
    for i in range(n - 1, -1, -1):
      if locked[i] == '1':  # 변경 불가능
        if s[i] == ')':
          low += 1
          high += 1
        else:
          low -= 1
          high -= 1
      else:  # 변경 가능
        low -= 1  # 최악의 경우 모두 '('로 취급
        high += 1  # 최선의 경우 모두 ')'로 취급

      if high < 0:  # '('가 너무 많아서 균형 불가능
        return False
      low = max(low, 0)  # low는 음수가 되지 않도록 보정

    return True

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.