문제

소괄호 '(' , ')'로 구성된 문자열 s가 주어집니다. 이 때 괄호의 짝이 맞는지 판별하는 solution() 함수를 구현하세요. 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄되며, 이때 반드시 열린 괄호가 닫힌 괄호보다 먼저 와야합니다.
이런 식으로 괄호를 없애는 과정을 반복했을 때, 남아있는 괄호가 없으면 짝이 맞다고 할 수 있습니다.

---

권장 시간: 30분
권장 시간 복잡도: O(N)
출제: 저자 출제

---

제약 조건

• s의 길이는 최대 10만이며, 빈 문자열인 경우는 없음
• 괄호의 짝이 맞으면 True, 짝이 맞지 않으면 False를 반환

---

풀이

닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라 닫힌 괄호가 나오기 바로 전 즉, 가장 가까운 (최근) 열린 괄호와 상쇄
'최근' 이라는 키워드를 보고 스택을 떠올리는 감각을 키우자

1. 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시
2. 닫힌 괄호가 나오면 팝 연산을 통해 최근 등장했던 열린 괄호 중 아직 상쇄하지 않은 열린 괄호를 확인하고 상쇄

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

---

시간 복잡도

• N은 s의 길이
• s를 순회하며 괄호의 쌍을 확인하므로 시간 복잡도는 O(N)