사용자 도구

사이트 도구


ps:problems:boj:11899

괄호 끼워넣기

ps
링크acmicpc.net/…
출처BOJ
문제 번호11899
문제명괄호 끼워넣기
레벨실버 3
분류

괄호문자열

시간복잡도O(n)
인풋사이즈n<=50
사용한 언어Python 3.13
제출기록32412KB / 40ms
최고기록32ms
해결날짜2025/02/16

풀이

  • 우선 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)

코드

"""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()

토론

댓글을 입력하세요:
I X N W᠎ O
 
ps/problems/boj/11899.txt · 마지막으로 수정됨: 2025/02/16 13:35 저자 teferi