올바른 괄호

프로그래머스 - 올바른 괄호

문제 설명

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

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

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

제한 사항

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

입출력 예

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

풀이

def solution(s):
    stack = []

    for parenthesis in s:
        if not len(stack) or stack[-1] != '(' or parenthesis != ')':
            stack.append(parenthesis)
        else:
            stack.pop()

    return len(stack) == 0

해결 과정

프로그래머스의 "괄호 변환" 문제를 먼저 풀었던 사람이라면 바로 해결 방법을 떠올릴 수 있는 문제였다.

stack을 사용하여 s의 맨 앞 문자부터 집어넣는다. 대신, stack의 마지막이 "(" 문자고, 자신의 문자가 ")" 문자라면 괄호의 한 쌍이 만들어진 것이므로 pop을 진행한다.

이렇게 했을 때 stack에 남아있는 것이 없다면 해당 문자열은 올바른 괄호라고 할 수 있다.

다른 사람의 풀이

def solution(s):
    x = 0
    for w in s:
        if x < 0:
            break
        x = x+1 if w=="(" else x-1
    return x==0

stack의 push나 pop을 진행하면 메모리 공간이 동적으로 늘었다 줄었다 한다. 물론 마지막 요소에 대해서만 진행되므로 shift 현상이 일어나지 않아 효율성 면에서 나쁘지 않다.

하지만, 다음과 같이 변수에 0을 넣고, "(" 문자일 때는 1을 더하고, ")" 문자일 때는 -1을 한다.

첫 번째 문자가 ")"라면, 이후 문자를 볼 것도 없이 잘못된 괄호이므로 바로 반복문을 탈출한다.

이게 효율성 면에서 봤을 때 굉장히 좋은 코드라는 것을 느꼈다.