수리링의 데이터교실

한동안 코테를 잠시 안풀었더니

효율성 테스트를 통과하는데 조금 헤맸던 문제입니다..!

Stack 알고리즘을 활용하지 않고 문제를 풀었을 때 테스트 케이스 정확성은 통과하는 데 문제가 없으나, 효율성 테스트를 통과하기 어려우실 수 있습니다. 효율성 테스트까지 통과할 수 있는 문제 풀이 방법을 알려드릴게요 :)

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

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

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

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

1.

먼저 빠른 탈출을 위해 다음 4가지 경우에는 함수를 False로 얼리 리턴하도록 설정해주겠습니다.

• 주어진 문자열이 ")" 로 시작하는 경우
• 주어진 문자열이 "(" 로 끝나는 경우
• 주어진 문자열의 길이가 홀수인 경우
• 주어진 문자열이 ")" 또는 "(" 한 종류로만 이루어진 경우

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

2.

다음으로 stack 리스트를 선언해주도록 하겠습니다.

    stack = []

우리는 stack 리스트에 "(" 열기 괄호만 넣어줄 것입니다.

왜 열기 괄호만 넣어줄까요? 예시를 통해 한번 확인해 봅시다.

문자열 s = "(((())"가 있다고 합시다. 딱 봐도 열기 괄호는 4개인데 닫기 괄호는 2개여서 짝이 맞지 않는다는 것을 알 수 있습니다. 우리는 for루프를 통해 0번째 자릿값부터 차례대로 돌면서 해당 자리의 값이 "("이면 stack에 넣어주고, ")"이면 stack에 있는 열기괄호를 하나 빼 줄 것입니다.

    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()

s = "(((())"

1. 첫 번째 자리 "(" -> stack = "(" 
2. 두 번째 자리 "(" -> stack = "(", "("
3. 세 번째 자리 "(" -> stack = "(", "(", "("
4. 네 번째 자리 "(" -> stack = "(", "(", "(", "("
5. 다섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "(", "("
6. 여섯 번째 자리 ")" -> stack이 비어있지 않으므로 stack.pop()
   -> stack = "(", "("

    if stack:
        return False
    else:
        return True

이터레이션을 다 돌고 났을 때

stack이 비어 있으면 짝이 맞으므로 True

stack에 남은 값이 있다면 짝이 맞지 않는 것이므로 False를 리턴합니다.

결국 "("의 갯수와 ")"의 갯수가 동일한지 확인하는 것과 다름 없습니다. 다른 방법으로도 정확성 문제는 통과하는 데 어려움이 없으나, 효율성에 문제가 생기는 관계로 stack 알고리즘을 통해 효율성을 높여준 것이라고 보시면 되겠습니다.

3.

마지막으로 한 번에 코드를 보겠습니다.

def solution(s):
    if s[0] == ")" or s[-1] == "(" or len(s) % 2 == 1 or len(set(s)) == 1:
        return False

    stack = []
    for char in s:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    
    if stack:
        return False
    else:
        return True

감사합니다!