[프로그래머스 알고리즘 고득점 KIT] STACK & QUEUE : 올바른 괄호

프로그래머스 문제 보러가기

프로그래머스

 

 

문제 설명

- 괄호로 이루어진 문자열 주어짐

- '('문자로 열렸으면 반드시 짝 지어서 ')' 문자로 닫혀야 함

- 만족하면 True반환, 틀리면 False 반환

 

 

내 코드 

def solution(s):
    answer = True
    # 1. i가 여는 괄호로 시작해야함 / 여는걸로 끝나면 안됨
    # 2. 여는걸 만나면 +1
    # 3. 닫는걸 만나면 -1
    # 총 0이 되면 True
    sum = 0
    if (s[0] == ')' ) or (s[-1] =='('):
        return False
    
    for i in range(len(s)):
        if s[i] == '(':
            sum+=1
        elif s[i] == ')':
            sum-=1
        if sum <0:
            return False
    if sum ==0:
        return True
    else:
        return False

코드 풀이

1. 만약 문자열의 시작이 닫힌 괄호거나, 문자열의 끝이 열린 괄호면 False반환
2. 열린 괄호를 만나면 sum값 +1,
3. 닫힌 괄호를 만나면 sum값 -1
4. 모든 pair가 맞다면 최종적으로 문자열 순회를 마쳤을 때, sum값은 0이 됨을 이용

주의 : 위와 같이 작성 시, 일부 테스트 케이스를 만족하지 못함.

 

예를들어. '())(()'와 같은 문자열의 경우

- 열린괄호로 시작해 닫힌 괄호로 끝나고,

- 열린괄호와 닫힌 괄호의 수도 같다.

 

=> 틀린 괄호이지만 조건에서 잡아내지 못함. 

 

따라서 중간에 sum이 음수가 되는 경우를  체크하도록 함

-> sum이 음수가 된다는 것은 열린 괄호 수에 비해 닫힌 괄호 수가 많다는 것

=> False를 반환

 

더 나은 풀이

다른 사람(마엘, 야채구이)의 코드를 참조해 보았더니, 파이썬의 pop메소드를 사용

1. 문자열을 순회하면서 열린괄호를 만나면 빈 리스트에 열린괄호 append
2. 닫힌 괄호를 만나면 해당 리스트 요소를 pop
3. 만약 여기서 UnderFlow가 발생한다면, return False
   • under flow가 발생하는 경우는,
   • 닫힌 괄호로 시작해 빈 리스트에 pop하는 경우 -> 닫힌 괄호로 시작하는 경우 잡아냄
   • 중간에 닫힌 괄호의 수가 열린 괄호의 수보다 많아지는 경우 -> 내 코드에서 sum <0으로 표현했던 경우와 같음
4. 최종적으로 리스트가 비었는지, 즉 길이가 0인지 확인
   • pair가 다 맞다가 마지막에 열린 괄호로 끝나는 경우 잡아낼 수 있음