https://codeforces.com/contest/1520/problem/E
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 2 * 106)
• a string of length n

output :

• For each test case output the minimum number of moves you need to make to complete the level.
  각 테스트 케이스에서 level을 만들기 위해 필요한 최소의 횟수를 출력하시오.

조건 :

• In one move, you can move any sheep one square to the left or one square to the right, if the corresponding square exists and is empty.
  양의 좌, 우에 공간이 존재하고 비어있을 때 양을 왼쪽 혹은 오른쪽으로 움직일 수 있다.

• The game ends as soon as the sheep are lined up, that is, there should be no empty cells between any sheep.
  양을 한 줄로 줄 세웠을 때 게임은 종료된다.

---

어떻게 하면 양을 한 줄로 세울수 있을까???

왼쪽, 오른쪽

가장 왼쪽을 기준으로 양을 몰아버린다면?? 혹은 오른쪽으로 밀어버린다면???
이렇게 할 경우 가장 끝에 존재하는 애들이 의미없이 많이 움직여야 한다.

더 좋은 방법은??

중간

가장 중간에 위치한 놈을 찾아서 그 좌우에 가장 가까이 존재한느 양들을 갖다 붙여 버리는 거다.

구현

양들의 위치를 가지는 배열.
중앙에 위치한 양을 찾아서 빈 공간을 찾는다.
그리고 이 빈공간에 양을 넣어준다. -> 양이 움직여야 하는 횟수를 인덱스 - 인덱스로 구한다.

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = sys.stdin.readline().rstrip()
    stars = []
    ans = 0

    for idx, item in enumerate(data):
        if item == '*':
            stars.append(idx)

    if not stars:
        print(0)
        continue

    target = stars[len(stars) // 2]
    
    left_pos = target - 1
    right_pos = target + 1

    left_star = len(stars) // 2 - 1
    right_star = len(stars) // 2 + 1

    while left_star >= 0:
        ans += left_pos - stars[left_star]
        left_star -= 1
        left_pos -= 1

    while right_star < len(stars):
        ans += stars[right_star] - right_pos
        right_star += 1
        right_pos += 1

    print(ans)