<프로그래머스 문제풀이: 올바른 괄호> Level 2 - 파이썬

간단해 보이는 괄호 문제이다. 어디서 본 적이 있는 듯한 문제인데 기억이 안난다(백준에서 본 것 같기도 하고...)

시간 초과가 뜬 풀이

처음에는 while문으로 풀었는데 효율성 테스트 1,2번에서 계속 시간초과가 뜬다.

def solution(s):
    while True:
        temp = s
        s = s.replace('()', '')
        if s == '':
            return True
        if temp == s:
            return False

아마도 while문 때문에 그런듯 하다. 원래 이 코드의 취지는, s 문자열 안에 있는 ()를 빈 문자열로 대체해주고, 미리 정의 해놨던 temp 와 s 가 같으면 그 뜻은 while문안에서 더 이상 ()이 발견이 안된다는 뜻인데, 이 때 temp랑 s가 같으면 지속적으로 while문이 실행되었다는 뜻이므로 False를, 아니고 s 가 빈 문자열이 된다면 True를 되돌려주게 하려 했다. 하지만 이는 시간 초과가 떴으므로 다른 방법이 필요했다.

정답

def solution(s):
    if s.count('(') != s.count(')'):
        return False
    s = s.replace('()', '')
    if len(s) == 0:
        return True
    if s[0] == ')' or s[-1] == '(':
        return False
    return True

이번에는 while문을 사용하지 않고 하는 방법을 강구해야 했다:

1. 만약 '(' 과 ')'의 개수가 같지 않다면 틀린것이므로, False를 되돌려준다.
   
2. s = s.replace('()', '')를 해주고, len(s) == 0 이라면 바로 True를 되돌려준다. 이는 예를 들면()()와 같은 문자열을 실행시켰을 때 바로True`를 되돌려준다.
   
3. s = s.replace('()', '')를 실행시킨 뒤에 마지막 s[0] == ')' or s[-1] == '('을 실행시켜준다. 예를 들면 '())(()' 같은 경우는 1번의 경우를 만족하고, 2번처럼 s = s.replace('()', '')를 실행시키지 않고 바로 3번을 실행시켜준다면 True를 반환할 것이므로, 2번을 실행시켜주고 3번을 실행해야 한다. 2번을 실행하면 '())(()' 는 ')('가 된다.
   
4. 마지막에는 이를 모두 통과했다면 옳은 괄호이므로, True를 반환한다.
   

이 문제는 오히려 반례를 찾느라 힘들었다. 내 코드에 대한 반례를 찾을 수 있으면 빠르게 풀리는 문제였다.