문제

• 
• 시간 제한: 0.5초
• 메모리 제한: 512MB

Problem Analysis

Naive한 방법은, i부터 j까지 순서대로 stack을 이용하여 top에 '('가 있을 때 ')'이 다음으로 오면 pop을 하고, 그 외에는 계속 push를 해주면서, 마지막에 stack이 비었다면 올바른 문자열로 판단하는 것이다. 그러나 이는 최악의 경우 시간 복잡도가 O(NM)이다. 이를 개선하고자, i부터 j를 검사했을 때 stack에 남아있을 ')'와 '('의 개수를 저장해 준다면, Segment Tree를 활용할 수 있다.

Algorithm

• construct ST
• ans Query

두 함수 모두 아래의 논리를 따른다.
i부터 j까지 계산했을 때 stack에 남아있을 ')'의 개수와, '('의 개수를 ST[idx]에 저장한다.
이때, 현재 node의 값을 계산할 때, left child와 right child로 들어가게 되는데, 왼쪽 구간의 남은 '('와 오른쪽 구간의 남은 ')'을 매칭시키고 난 뒤에, 최종적으로 남은 ')'와 '('를 저장한다.

Data Structure

• 남은 opening parenthesis와 closing parenthesis 값을 저장할 struct
• Segmen Tree, 각 node는 위의 struct 값을 저장

결과

Other

시간 복잡도는 O(M * logN)이다.
이처럼 구간에 대한 정보를 다룰 때는 Segment Tree가 제격이다.