[프로그래머스] 레벨2 올바른 괄호- 파이썬 python

• 올바른 괄호

darklight

sublimevimemacs

Python3 

문제 설명

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

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

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

제한사항

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

---

입출력 예

sanswer

()()	true
(())()	true
)()(	false
(()(	false

입출력 예 설명

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

 

 

1차 : 실패한 풀이

def solution(s):
    answer = True
    while True:
        temp = s.replace('()','')
        if s == temp:
            break
        s = temp
    if not s:
        return True
    else: return False

결과는 테스트케이스에서 기대한 값과 같게 나왔지만 시간초과의 이유로 효율성 점수가 낮게 나왔다.

백준에서도 괄호의 완전성을 따지는 비슷한 문제가 있었는데,

그 때도 완전한 괄호를 replace로 바꾸면서 반복했을 때 시간초과가 났던 기억이 있어 다른 방법을 생각했다.

 

2차: 성공

def solution(s):
    t = []
    for i in s:
        if i=="(":
            t.append(i)
        else:
            if t:
                t.pop()
            else: return False
    if t: return False
    else: return True

스택으로 풀면 해결할 수 있다.