테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 괄호 끼워넣기 ======

===== 풀이 =====
  * [[ps:tutorial:올바른 괄호 문자열]]의 응용.
  * 우선 score(최종점수)와 min_score(최소점수)를 구한다. 
  * 만약 min_score < 0 이면 올바른 괄호 문자열이 될수 없기 때문에, 0이상이 되게 하기 위해서 맨 앞에 -min_score 만큼의 '('를 추가해야 한다. 이렇게 되면 score 역시 -min_score 만큼 증가한다
  * score > 0 이면 올바른 괄호 문자열이 될수 없기 때문에, 맨 뒤에 score만큼의 ')'를 추가해야 한다.
  * 식을 정리하면, min_score>=0 일때는 답이 score가 되고, min_score<0 일때는 score - 2*min_score 가 답이 된다.
  * 시간복잡도는 O(n)
 
===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11899. 괄호 끼워넣기".

- Problem link: https://www.acmicpc.net/problem/11899
- Solution link: http://www.teferi.net/ps/problems/boj/11899
"""


def main():
    S = input()

    score = 0
    min_score = min(score := score + (1 if x == '(' else -1) for x in S)

    print(score - 2 * min(0, min_score))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}