[리트코드 921] 괄호 문자열을 유효하게 만들기 — 미짝 괄호 수 세기

원제: Minimum Add to Make Parentheses Valid

문제 요약

문자열 s에 괄호를 삽입해 유효한 괄호 문자열로 만들 때 필요한 최소 삽입 횟수를 반환한다. 코드는 왼쪽부터 괄호의 균형을 세어, 짝지을 여는 괄호가 없는 닫는 괄호와 마지막까지 짝지어지지 않은 여는 괄호를 각각 센다.

조건과 입출력

입력 s는 괄호 문자열이며 1 <= s.length <= 1000, 각 s[i]는 '(' 또는 ')'이다. 괄호는 문자열의 어느 위치에나 삽입할 수 있고, 반환값은 유효하게 만드는 최소 이동 횟수다.

예제와 문제 자료

예제 1: s = "())"이면 반환값은 1이다. 첫 번째 여는 괄호와 첫 번째 닫는 괄호가 짝을 이루고, 남은 닫는 괄호 앞에 여는 괄호 하나를 삽입하면 된다. 예제 2: s = "((("이면 반환값은 3이다. 여는 괄호 세 개 각각에 짝이 될 닫는 괄호가 필요하다.

풀이 아이디어

cnt는 지금까지 읽은 문자열에서 아직 짝을 찾지 못한 여는 괄호의 수를 추적한다. 닫는 괄호를 만났을 때 cnt가 0이라면 그 닫는 괄호 앞에는 짝이 될 여는 괄호가 없으므로, 여는 괄호를 하나 삽입해야 한다. 코드에서는 먼저 cnt -= 1을 수행한 뒤 cnt < 0인지 확인해 그 상황을 판별하고, 삽입 횟수인 answer를 늘린 다음 cnt를 0으로 되돌린다. 끝까지 남은 cnt개의 여는 괄호는 각각 닫는 괄호가 하나씩 필요하다. 앞부분에서 부족했던 여는 괄호와 마지막에 남은 여는 괄호는 모두 반드시 보충해야 하므로, 이 둘을 세는 방식으로 최소 횟수를 얻는다.

코드의 핵심

cnt는 아직 짝지어지지 않은 여는 괄호 수, answer는 필요한 삽입 수다. x == "("이면 cnt를 1 늘린다. 그 외에는 입력 조건상 x == ")"이므로 cnt를 1 줄인다. 감소 후 cnt < 0이면 현재 닫는 괄호에 대응할 여는 괄호가 부족했다는 뜻이다. 여는 괄호 하나를 삽입한 것으로 answer를 늘리고 cnt = 0으로 복구한다.

코드 추적 — 예제 1 s = "())":

반복이 끝난 뒤 answer += cnt를 실행한다. 이 예제에서는 cnt가 0이므로 반환값은 1이다. 예제 2에서는 cnt가 1, 2, 3으로 증가하고 answer는 0인 채 끝난다. 남은 cnt를 더해 반환값은 3이 된다.

제출 코드

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        cnt = 0
        answer = 0
        for x in s:
            if x == "(":
                cnt += 1

            else:
                cnt -= 1

            if cnt < 0:
                answer += 1
                cnt = 0

        answer += cnt
        return answer

복잡도

문자열 길이를 n = len(s)라 하면, 각 문자를 한 번씩 처리하므로 시간 복잡도는 O(n)이다. cnt와 answer만 사용하므로 보조 공간은 O(1)이며, 별도의 결과 저장 공간은 사용하지 않는다.

복습 포인트

닫는 괄호가 부족한 경우는 매번 즉시 여는 괄호 하나를 삽입한 것으로 계산한다. 마지막의 answer += cnt를 빼면 끝에 남은 여는 괄호를 보충하는 횟수가 누락된다.

출처

문제 원문