[Python] L2 - 올바른 괄호

문제 분석 및 정답 도출

① "("로 시작하는가?

• 시작한다면?
  • "("의 수, "}"의 수 확인하기

• 그렇지 않다면? 
  • return False

② "("의 수 =="}"의 수 return True

else: return False

 

① , ② 와 같은 생각에 따라 테스트 케이스는 합격했다... 그러나 다른 케이스에서는 안 된다 한다.

def solution(s):
    start_count = 0
    finish_count = 0
    
    for i in range(len(s)):
        if s[0] == "(":
            if s[i] == "(":
                start_count += 1
            else:
                finish_count += 1
        else:
            return False
    
    if start_count == finish_count:
        return True
    else:
        return False

무엇이 문제일까?? 만약 "())("일 경우 False이어야하나, 내 코드에서는 True가 나온다.

아하 결론은 "("를 만나면 ")"가 있는지 확인하고 넘어가는 식으로 해야겠다는 생각이 들었다만... s의 길이가 100,000 이하의 자연수라면, 시간 복잡도가 될텐데... 그렇다면 무언가 방법이 있는게 아닐까...?

 

그래 스택과 큐... 시작과 끝맺음에 대한 여부를 묻는다면, '스택과 큐' 생각하자!!

다음 그림을 통해 순서도를 작성해보면...?

• "("이면 append()
• 아니면 
  • stack에 "(" 있으면, "(" pop()
  • stack에 없으면, return False

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

---

업데이트(2023.04.17)

pop을 사용해야지 시간 초과가 안 뜬다! remove 안 돼...!!