프로그래머스 LV2 올바른 괄호

문제

풀이

문제 분류는 스택으로 되어있어서 스택으로 풀으면 효율적인가 했지만,

다른 문제 풀이가 더 효율적이여서 이상했던 문제이다.

우선 스택 문제풀이 과정이다.

def solution(s):
    stack = []
    for i in s:
        if len(stack) == 0 and i == ')':
            return False

        if i == ')' and stack[-1] == '(':
            stack.pop()

        if i == '(':
            stack.append('(')

    return False if len(stack) != 0 else True

스택에 값이 0개일 때 ')'가 들어오면 바로 False를 반환하게 하고,

for문을 전부 다 돌았을 때 스택에 값이 하나라도 있어도 False를 반환하게 하였다.

이렇게하면 시간복잡도와 공간복잡도가 전부 O(N)만큼 소요된다. (s의 길이 만큼)

 

다른 풀이

def solution(s):
    answer = True
    
    count = 0
    
    for i in s:
        if i == '(':
            count += 1
        elif i == ')':
            count -=1
        if count<0:
            answer = False
            break
    if count>0:
        answer = False
    return answer

스택에 값을 넣으면 공간복잡도가 늘어나므로, 

for문을 돌며 count의 값을 통해서 관리하도록 하였다.

이러면 공간복잡도는 O(1)이 되고, 시간복잡도는 O(N)이 되어 더 효율적이다.

비교적 쉬운 문제지만 다양한 방법으로 생각해보면서 알고리즘 재활훈련에 도움이 되었다.