괄호의 값 비교

• 처음에는 괄호열의 값을 구하는 함수를 만들고, A와 B의 값을 각각 구해서 비교하면 된다고 생각했다.
• 괄호열의 값을 구하는것은 실버2 문제인 2504보다도 더 간단한 형태인데도 난이도가 골드로 측정되어있어서 좀 의아했지만, 일단 구현을 했다.
• 제출하니까 서브태스크 3부터는 시간 초과. 시간복잡도는 O(n) 이고 n은 최대 3백만이니까 이게 안돌아갈수는 없을것 같은데하고 당황하면서 코드에서 잘못 구현한 부분이 있는지를 한참 살폈다.
• 한참 고민하다가 뒤늦게 떠오른 것은, 괄호열의 값이 최대 2^(n/2) 까지도 올라갈수 있다는 것. 이렇게 큰수들을 갖고서 덧셈/곱셈을 반복하는 바람에 시간초과가 난것 같았다.
• 정확한 값을 구하지 않고 크기비교만 하는 방법을 생각해봤으나 만만치는 않았다. 정확한 값을 그냥 구하는 대신에 로그를 취한 값을 구하는 것도 생각해봤지만 역시 잘 안될것 같았다. 정확한 값을 2진수를 의미하는 배열에 채우는 방법을 떠올렸고, 이방법이 깔끔해보여서 이렇게 하기로 했다.
• 괄호열의 값은 모든 ()형태에 대해서, 그 앞에 있는 '('의 갯수 - ')'의 갯수 d를 구해서 2^d을 더해주면 된다. 2^d를 정수로 계산해서 더하는 대신에 배열의 d번째 칸에 1을 추가하는 식으로 처리했다.
• 이렇게 구현한 결과, 2등보다 약 3배 빠른, 1100ms 정도에 통과될수 있었다.
• 시간복잡도는 여전히 O(n)이다.

"""Solution code for "BOJ 22343. 괄호의 값 비교".

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

import itertools


def calc_score(string, max_len):
    count = [0] * max_len
    d = 1
    for prev, cur in itertools.pairwise(string):
        if cur == '(':
            d += 1
        else:
            d -= 1
            if prev == '(':
                count[d] += 1
    for i, v in enumerate(count):
        if v > 1:
            q, r = divmod(v, 2)
            count[i + 1] += q
            count[i] = r
    return count[::-1]


def main():
    T = int(input())
    for _ in range(T):
        A = input()
        B = input()
        max_len = max(len(A), len(B)) // 2 + 1
        a_score = calc_score(A, max_len)
        b_score = calc_score(B, max_len)
        if a_score > b_score:
            print('>')
        elif a_score < b_score:
            print('<')
        else:
            print('=')


if __name__ == '__main__':
    main()