[프로그래머스 lv2]올바른 괄호

문제설명

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

 

"()()" 또는 "(())()" 는 올바른 괄호입니다.

")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

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

 

제한사항

문자열 s의 길이 : 100,000 이하의 자연수

문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

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

 

입출력 예 설명

입출력 예 #1,2,3,4

문제의 예시와 같습니다.

 

문제 해결 방법

예시를 찬찬히 살펴보자. 

 

'('를 괄호가 열렸다고 표현하고, ')'를 괄호가 닫혔다고 표현하겠다. 

 

괄호가 열려있을 때, 괄호가 열릴수 있음 

괄호가 열려있을 때, 괄호가 닫힐 수 있음

괄호가 닫혔을 때 괄호를 열든 다시 닫든 할 수 있지만, 괄호가 닫히는것 부터 시작하면 안됨

 

이건 완전히 스택이다. 

 

괄호가 열려있다는 것을 push, 닫힌다는 것을 pop으로 표현한다고 했을 때 위에 있는 말에 대입 해보자. 

 

push할 때, push할 수 있음 

push할 때, pop할 수 있음

pop후에 push든 pop이든 할 수 있지만, pop부터 시작하면 안됨

 

이건 완전히 스택이다. 

 

pop부터 시작하면 안되는 이유는 스택에서, 스택이 비었을때 pop을 하면 더이상 pop할 게 없어서 따로 처리를 안해주면 오류가 생긴다. 

 

s에 대한 조회가 끝났을 때 stack에 뭔가 남아있으면 false이다. 

그런데 스택이 비었는데 )가 나오는 경우가 있을 수 있으니, 그럴때는 스택에 뭔가 남아있어서 False하는 경우와 구분하기 위해서 realF라는 변수에 0, 1을 넣어서 체크했다. 

 

코드 구현

def solution(s):
    answer = True
    
# (는 스택에서 push역할을 하고  )는 pop역할을 함 
# 스택이 빈 채로 끝나지 않으면 false임 

    stack = []
    realF= 0
    for i in range(len(s)):
        if s[i] =='(':
            stack.append(1)
        else:
            if len(stack)<1:
                answer= False
                realF = 1
                break
            else:
                stack.pop()
    
    if stack or realF == 1:
        answer = False
    else:
        answer = True
    
    return answer

 

시간/공간 복잡도

최악의 경우 n 임 

 

최적화 및 개선

어디를 최적화 해야하는지 잘 모르겠다! 

 

어려웠던 점

없었다 ^__^