Level 2 올바른 괄호 Python

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

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

 

최종 풀이

• GitHub github.com/hwayeon351/Programmers-Algorithms

hwayeon351/Programmers-Algorithms

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

 

 

---

풀이 과정

풀이 시간  14분

 

 이 문제는 Stack을 활용하면 문자열의 길이만큼만 탐색해서 문제를 해결 할 수있다. 이전에 푼 프로그래머스 Level 2 짝지어 제거하기와 비슷하다. 짝지어 제거하기 문제는 아래 참고를 확인하면 된다.

 

Stack 활용하기

 문자열 s의 길이 만큼 다음 과정을 반복한다.

• len(stack) == 0인 경우,

1. 문자 i == ")"인 경우는 s 문자열이 ")"로 시작하거나, 이전에 "()"쌍이 있어 stack에서 pop() 한 이후 처음 들어온 문자가 ")"인 경우이다. 이때는, 나머지 문자열을 따져주지 않아도 올바른 괄호가 아니므로 return False 해준다.
2. 문자 i == "("인 경우는 s 문자열이 "("로 시작하거나, 이전에 "()"쌍이 있어 stack에서 pop() 한 이후 처음 들어온 문자가 "("인 경우이다. 이때는, 다음 ")"가 들어와서 pop() 해야하므로 stack에 i를 쌓아준다.

 

• len(stack) != 0인 경우,

1. i == "("인 경우, stack에 i를 쌓아준다.
2. i == ")"인 경우, stack의 top에 있는 "("를 pop() 해준다.

for문이 끝난 후, len(stack) == 0인 경우, 문자열 s가 올바른 괄호이므로 True를, 아니면 False를 반환한다.

 

 

 

---

참고

• 2021/01/11 - [C++] - [STL] Stack

[STL] Stack

• 2021/01/14 - [코테 노트/프로그래머스] - Level 2 짝지어 제거하기

Level 2 짝지어 제거하기