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

김아현·2023년 4월 14일
0

코딩테스트

목록 보기
3/26
post-thumbnail

올바른 괄호 파이썬 풀이

문제설명

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

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

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


제한 사항

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

접근 방법

  • 입출력 예제 각각을 잘 살펴보자.
sanswer
"()()"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 Falsereturn ans == 0으로 더 줄여 쓸 수 있다!

TIL

  • 문제 조건을 잘 살펴보자. 이 문제는 입출력 예제를 잘 살펴보고 내가 설계한 변수의 흐름만 잘 파악하면 금방 풀어낼 수 있다.
profile
멘티를 넘어 멘토가 되는 그날까지 파이팅

0개의 댓글