프로그래머스 고득점 kit(유형정리) - 올바른 괄호

코딩테스트 연습 - 올바른 괄호 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제 설명

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

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

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

제한사항

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

 

입출력 예

s                                                                                                       answer

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

 

 

문제는 위와 같다. 이상하게 짝지어진 경우에는 false를 반환하고, 제대로 괄호가 짝지어진 경우에는 true를 반환하면 된다. 확실히 Level 2라 그런지 스택/큐를 사용하는 것을 알고도 어떻게 풀어야 할지 한참 고민했고, 몇 번이나 코드를 실행하면서 이리저리 돌려봤던 거 같다.

 

※ 알고리즘

1. 빈 stack 하나를 선언한다.

2. s 문자열 안에서 반복문으로 처리한다.

3. i가 "(" 이면 일단 append 시켜준다.

4. i가 ")" 일 경우 빈 stack에서는 false를 반환한다. -> ")" 문자열이 제일 처음 나올 수 없기 때문

5. 빈 stack이 아니라면 하나씩 pop 시켜준다. 이렇게 해야 ()의 짝을 맞추어 줄 수 있다.

6. stack이 비어있지 않으면 잘못되었다는 false를 반환한다. -> 이 작업을 해주지 않으면 비어있지 않아도 true가 반환되어 마지막 문제에서 정답이 다르게 나온다.

 

def solution(s):
    answer = True
    stack = []
    
    for i in s:
        if i == '(':
            stack.append(i)
        else:
            if stack == []:
                answer = False
                
            else:
                stack.pop()
    
    if stack != []:
        answer = False

    return answer

 

이렇게 해결을 할 수 있었다. 마지막 stack이 비어있지 않은 경우를 처리해 주지 못해서 정답 제출만 몇 번을 하면서 수정을 했던 것 같다. pop 부분도 굉장히 핵심적인 부분이다. stack에서 pop을 시키면서 () 쌍을 찾아 주는 것이 핵심이다.