3. 올바른 괄호

 

문자열 s 가 ( 로 시작하여 ) 로 끝나야 한다는 뜻이다. 

그렇다고 ( )) ( 가 올바르다는것도 아니다. 

 

바로 생각나는 방법은 

 

올바른 문자열 s 의 괄호중 맨 안쪽 괄호는 결국 ()  인 문자가 나오게되며

해당 괄호를 제거하더라도 다시 () 괄호가 계속해서 1개 이상 존재하고 

마지막엔 "" 으로 남게 될것으로 예상된다. 

 

즉 반복문을 사용하여 () 를 -> "" 으로 바꾸어서 계속해서 줄여나가면 해결할수있을꺼같다.

 

def solution(s):

   

    # () 가 있으면 지우기

    while "()" in s:

        s = s.replace("()","")  

   

    # 판단

    if len(s) > 0 :

        return False

    return True

 

결과는 시간초과가 났다. 

 

() in s 가 문제인걸까 

while 의 반복 횟수가 문제인걸까 

replace 가 문제일수도있다.

 

정말 극단적으로 1개씩 지워진다고 생각하면 굉장히 많이 반복하게 되는것 같다.

 

---

 

2번째 방법으로는 괄호가 있는 문자열을 변형하지 않고 판단하는 방법으로 

 

( = +1 

) = -1 로 생각하는 방법이다.

 

문자열 s 를 읽으면서 해당 문자에 대해서 +1 또는 - 1을 누적하며 누적 값이 0보다 작아지는 경우 false 가 되게된다. 

 

예를 들면 

(  )  )  (  의 경우

0 -> 1 -> 0 -> -1 -> 0  과 같으며 false 가 되게 된다. 

 

def solution(s):

    count = 0

   

    for word in s:

        if word == "(" :

            count += 1

        else :

            count -= 1

        # 즉시 중단

        if count < 0 :

            return False

   

    # ( 가 더 많을 경우

    if count != 0 :

        return False

    return True