코딩 공부/Leetcode

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

일하는 공학도 2025. 1. 12. 23:50
728x90

난이도 : Medium

 

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

 

동일한 길이를 가진 괄호 문자열 s와 locked 문자열이 있다.

괄호 문자열 s의 경우는

  1. 문자열이 ()인 경우
  2. A와 B가 연결된 괄호 문자열인 AB (ex. "()" or ")(" )
  3. (A) (ex. "(()" or ())" )

그리고 locked[i]이 1이라면 s[i]를 바꿀 수 없음

s를, 위의 조건을 만족하는 괄호 문자열이라면 True를 반환

 

해답으로 먼저 고안한 것

1. example 3에서 나왔듯이, 괄호가 열리면 안된다.

    즉, 문자열 길이가 홀수라면 무조건 False

2. 열린 괄호는 닫혀야 한다.

    기존의 괄호 + 바뀔 수 있는 것이, 바꿀 수 없는 다른 괄호 보다 적으면 False

    같거나 더 크면 "("와 ")"의 수를 동일하게 맞출 수 있기 때문

 

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

        count = 0
        for i in range(n):
            if s[i] == "(" or locked[i] == "0":
                count += 1
            else:
                count -= 1
            if count != 0:
                return False

        count = 0
        for i in range(n-1, -1, -1):
            if s[i] == ")" or locked[i] == "0":
                count += 1
                print(i)
            else:
                count -= 1
            if count < 0:
                return False

        return True

 

count = 0을 두 번 setting하고 for문을 2개를 둔 이유는, 처음엔 한 쪽의 갯수만 세고 대충 동일한가만 세면 될 줄 알았다.

번거롭지만 "("와 ")"일 때 각각 False인 case를 setting하였다.

코딩할 때에는 대충이라는 건 안되긴 한다는 생각이 들긴 했다..

 

Runtime : 101ms (60.52%)

Memory : 18.82MB (30.84%)

728x90