[LV2/스택/큐] 올바른 괄호

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

프로그래머스

 

[풀이]

---

처음풀이

def solution(s):
    while True:
        if '()' in s:
            s = s.replace('()', '')
        else:
            break
            
    if s == '':
        return True
    else :
        return False

• 시간 복잡도 생각안하고 가장 간단히 짜본 코드
• 효율성 문제에서 걸렸다.
• 일단 문자열 s에서 '()'를 찾아서 제거하는 과정을 반복하는데, 이 때 문자열을 제거하고 재구성하기 때문에, 최악의 시간복잡도는 O(n^2)
• 간단한 풀이지만 시간복잡도를 봤을 때 좋지 않은 코드

 

나중풀이

def solution(s):
    open = 0
    close = 0
    
    for i in s:
        if i == '(':
            open += 1
        else :
            close += 1
        if open < close:
            return False
        
    if open != close:
        return False
    return True

• 열린 괄호에 대해서 open에 숫자를 추가해주고, close에 숫자를 추가해주면서 close 숫자가 더 클 경우 바로 False 리턴
• 전부 실행을 마쳤으면 값을 비교해 본 뒤, open close 숫자가 다르면 False 리턴
• 시간복잡도는 O(n)

 

[풀이 후기]

---

스택/큐라고 명시는 되어있지만, 다른 방식으로 접근하는 게 더 직관적인 풀이일 때가 더 많은 것 같다. 시간복잡도를 생각하면서 구현하려고 하지만, 보기 쉬운 코드를 더 선호하는 느낌이다..,,

일단 알고리즘을 공부하고 있으니까 시간복잡도 철저히 생각하면서 풀어봐야겠다.