[Programmers] 올바른 괄호

문제

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

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

제한 사항

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

풀이

1. 첫번째 풀이
   while문과 replace를 활용하여 코드를 작성함. --> 정확성 테스트는 통과했으나 시간 복잡도에서 문제가 발생함.

def solution(s):
    answer = True
    while True:
        if "()" in s:
            s = s.replace("()", "")
        else:
            break
    if s:
        return False
    else:
        return True

2. 두번째 풀이
   Stack을 활용하여 시간 복잡도 문제를 해결함.

def solution(s):
    stack = []
    
    for i in s:
        if stack == []:
            stack.append(i)
        elif stack[-1] + i == "()":
            stack.pop()
        else:
            stack.append(i)
    if stack:
        return False
    else: return True

 Code를 실행시킨 결과 정답을 맞출 수 있었으나, 좀 더 개선할 방안을 고민해보았다.

def solution(s):
	stack = []
    
    
    for c in s: # char의 c로 변경
    	if not stack: # if stack == []를 좀 더 Pythonic하게 변경
        	stack.append(c)
        elif stack[-1] + s == "()":
        	stack.pop()
        else:
        	stack.append()
    return not stack # 마지막 return 조건을 간단하게 변경

3. ChatGPT가 작성한 결과

def solution(s):
    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if stack:
                stack.pop()
            else:
                return False
    return not stack

 시간 복잡도 측면에서 약 절반 가량의 시간을 절약하고 있으며, 좀 더 간결하고 명확한 코드를 작성하고 있음.