[스택/큐] 프로그래머스 올바른 괄호 - 파이썬

올바른 괄호 파이썬 풀이

문제설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다.

예를 들어"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

---

제한 사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

---

입출력 예제

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

• 입출력 예제 각각을 잘 살펴보자.
• 스택을 이용해서 풀어도 되지만 괄호 판별을 위한 ans 변수만 있다면 문자열을 한 번만 순환해도 해결할 수 있는 문제라고 생각했다.
• 3번 예제처럼 ")"로 시작하는 문자열은 아예 시작부터 올바르지 못하기 때문에 제외하고 시작하는 것으로 접근했다.

1차 작성 코드

def solution(s):
    ans = 0
    # ")"로 시작하는 문자열을 사전 차단
    if s[0] == ")":
        return False

    for c in s:
        if c == "(":
            ans += 1
        elif c == ")":
            ans -= 1 
    return True if ans == 0 else False

처음 시도한 코드는 다음과 같이 작동하도록 작성했다.

• 주어지는 문자열 s의 각각의 괄호를 c라 하자
• 문자열을 돌면서, c가 '('인지 판별한다. '('라면 ans를 증가시키고, ')'면 반대 괄호이므로 ans를 감소 시킨다.
• 그래서, "(())" 처럼 주어지면, ans가 2가 되었다가 다시 짝을 만나 0으로 줄어든다.
• ans == 0 이면 짝이 알맞으므로 True를, 아니면 False를 리턴하도록 했다.

1차 작성 코드의 문제점

• 테스트 케이스 4, 5, 11, 18번에서 실패했다. 효율성은 통과했다.
• 여기서 어떤 문제가 발생한걸까? 반례가 뭘까? 생각해보니, "(()))("같은 케이스가 있다면 이는 단순하게 짝 개수를 세는 ans변수로 판별하면 오답이 된다.
• "(())"가 왔다면 다음 차례는 무조건 "("여야 한다. 이런 조건을 만족할 수 있도록 코드를 수정해보았다.

1차 코드 수정하기

def solution(s):
    ans = 0
    # ")"로 시작하는 문자열을 사전 차단
    if s[0] == ")":
        return False

    for c in s:
        if c == "(":
            ans += 1
        elif c == ")":
            ans -= 1 
        if ans < 0 :
            return False    
    return True if ans == 0 else False

입출력 예제를 여러가지 생각해보면 조건 수정 하나로 간단하게 해결할 수 있다!
1. "(())"이후에 ")("가 왔다고 생각해보자."(())"까진 ans=0을 유지하고 있다.
2. 그러면, "(())" 이후엔 c == ")" 조건에 의해 ans-=1이 실행된다.
3. ans = -1이 된다.
4. ans = -1이 되려면 ")"가 먼저 오거나 짝이 맞지않는 조건 밖에 없다. 그러므로, 이때 return False를 하면 된다.
아, 그리고 여기서 return True if ans == 0 else False은 return ans == 0으로 더 줄여 쓸 수 있다!

TIL

• 문제 조건을 잘 살펴보자. 이 문제는 입출력 예제를 잘 살펴보고 내가 설계한 변수의 흐름만 잘 파악하면 금방 풀어낼 수 있다.