[파이썬] 올바른 괄호

programmers.co.kr/learn/courses/30/lessons/12909

코딩테스트 연습 - 올바른 괄호

 

문제 설명

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

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

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

제한사항

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

---

입출력 예

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

 

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

 

★ 나의 풀이

 

# 효율성에서 실패 뜬 코드
def solution(s):
    stack=[]
    i=0
    
    while i<len(s):
        stack.append(s[i])  
        i+=1
        if len(stack)>1 and stack[-2]=="(" and stack[-1]==")":
            stack=stack[:-2]

    return True if len(stack)==0 else False

 

효율성에서 탈락한 코드 ㅠ.ㅠ

다른 사람들 보니 "("만 리스트에 넣고 ")"만나면 넣어둔 "("를 pop한다.

 

# 최종 코드
def solution(s):
    stack=[]
    i=0
    
    while i<len(s):
        if len(stack)==0 or s[i]=="(":
            stack.append(s[i])   
        else:
            stack.pop()
        i+=1
        
    return True if len(stack)==0 else False​

 

리스트 stack에 아무것도 없거나 s[i]가 "("일 때 stack에 "("를 추가한다. stack[i]가 ")"면 pop한다.

반복문이 끝난 후 stack에 남아있는 값이 없으면 True, 그렇지 않다면 False를 반환한다.

 

★ 다른 사람 풀이

 

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

 

문자열 s에서 꺼낸 문자 w가 "("라면 x를 1증가시킨다. w가 ")"일 때는 x를 1 감소시킨다.

x가 0이면 괄호가 짝이 맞다는 것이다.