프로그래머스 연습 문제 - 올바른 괄호

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

프로그래머스

올바른 괄호

문제 설명

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

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

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

제한사항

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

---

입출력 예sanswer

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

입출력 예 설명

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

---

[문제 해설]

 

포인트 1: 이 문제는 스택의 원리를 이용해서 문제를 풀면 쉽습니다.

포인트 2: 우선 '(' 와 ')' 만나면 우리는 이 둘을 생각하지 않아도 된다.

 

결론적으로 이 두 포인트로 문제를 해결하면 된다.

 

0. s를 순회하면서 조건에 맞게 스택에 넣고 제거하는 작업을 할 것입니다.

1. 우선 stack에 값이 없는데 ')' 들어온다면 해당 괄호는 영원히 삭제되지 않습니다. 고로 false 리턴

2. 스택에 있을 경우 4가지를 나눠서 문제를 풉니다.

2-1. stack [-1] = '(' 과 s = ')'  // 둘이 괄호가 완성되는 상태 즉 stack.pop, s[idx] 값은 무시하면 됩니다.

2-2. stack[-1] = '(' 과 s = '(' // 이 경우 스택에 '(' append

2-3. stack [-1] = ')'과 s = '(' // 스택에 s값 append

2-4. stack[-1] = ')' 과 s = ')' // 스택에 s값 append

3. 이렇게 s의 순회를 마치고 s에 값이 존재하면 완성되지 않은 괄호 형태의 구조가 있다는 것이므로 => false

3-1. stack 비었다면 s문자열은 모두 괄호가 완성됐다는 뜻이므로 => true

 

* 4가지의 조건을 검사할 때 코트 더 짤게 쓸 수 있어 보이죠? 굳이 일일이 검사할 필요가 없습니다. 다만 설명을 위해 이렇게 작성했고, 코드 리팩터링은 이 글을 보시는 분이 있고 설명이 필요하시다면 한 번 해보시기를 바랍니다.

 

---

[코드]

def solution(s):
    answer = True
    
    stack = []
    for bracket in s:
        if not stack:
            if bracket == ')':
                return False
            else:
                stack.append('(')
        else:
            if bracket == '(':
                stack.append('(')
            else:
                if stack[-1] == '(':
                    stack.pop()
                else:
                    stack.append(')')
                    
    if not stack:
        return True

    return False

---

후기

 

이 문제를 풀면서 스택을 쓰겠다는 생각을 못하면

난감하고 어렵다. (많은 조건문이 들어가질 거라고 예상됩니다.)

못했다면 연습이 필요할 듯싶습니다.