[프로그래머스] 올바른 괄호 level2 - python

https://school.programmers.co.kr/learn/courses/30/lessons/12909

프로그래머스

 

 

 

문제 설명

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

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

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

 

 

 

 

 

 

제한사항

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

 

 

 

 

 

 

입출력 예

 

 

 

---

이 문제는 괄호가 올바르게 잘 배치되어 있는지 판별하는 문제이다. 즉, 열린 괄호 ' ( ' 가 있으면 그에 맞게 닫힌 괄호 ' ) ' 도 있어야 한다는 것이다. 

 

이 문제를 접근하기 위해서 반드시 False인 조건들은 먼저 제거해주었다. 가장 먼저 오는 괄호가 닫힌 괄호 ' ) ' 인 경우가 바로 그것이다.

 

다음으로 열린 괄호 ' ( ' 가 들어간 후 닫힌 괄호 ' ) ' 가 들어오는 만큼 열린 괄호 ' ( ' 를 제거해주는 방식을 사용하였다. 

 

 

 

 

 

 

 

 

deque 사용

from collections import deque

def solution(s):
    queue = deque()
    
    # )으로 시작하는 문제는 False
    if s[0] == ')':
        return False
    
    for ss in s:
        if ss == '(':
            queue.append(ss)
            
        else:
            queue.popleft()
            
    if queue:
        return False
    else:
        return True

앞서 말한 열린 괄호 ' ( ' 가 들어간 후 닫힌 괄호 ' ) ' 가 들어오는 만큼 열린 괄호 ' ( ' 를 제거해주는 방식을 사용하기 위해 deque 를 사용하였다.

 

하지만 위 코드를 사용하면 효율성 문제에 걸려 통과가 되지 않았다. 고로 효율성을 챙기기 위해 다른 방식으로 접근하였다.

 

 

 

 

 

 

 

def solution(s):
    stack = []
    for c in s:
        if c=='(':
            stack.append(c)
            #스택에 (가 더이상 없거나 스택에서 pop을 할때 팝연산을 하고나서 "("가 있을 때
        elif not stack or stack.pop() != '(':  # == ')'
            return False 
            #stack이 있으면 false를 리턴하고 없으면 True를 리턴
            
    return False if stack else True

다음 코드는 위 코드와 비슷하나 deque에 괄호를 집어넣고 제거하는 부분을 뺀 코드이다. 확실히 불필요한 연산이 제거되니 효율성 부분에서 향상되는 모습을 보여주었다.