동전 쌍 뒤집기
면접 대비시간 제한2초메모리 제한1024 MB
이웃한 두 동전이 같은 면일 때 둘을 함께 뒤집는 조작으로 모든 동전을 앞면으로 만들 때, 필요한 최소 조작 횟수를 구하거나 불가능하면 -1을 출력한다.
문제
N개의 동전이 일렬로 놓여 있다. 각 동전은 앞면이나 뒷면이 보이도록 놓여 있다.
당신은 다음의 조작을 원하는 만큼 반복할 수 있다.
- 서로 이웃하면서 같은 면으로 놓여있는 두 개의 동전을 선택하여 둘 다 뒤집는다.
앞면이 보이는 동전을 뒤집으면 뒷면이, 뒷면이 보이는 동전을 뒤집으면 앞면이 보이게 된다.
각 동전의 상태가 주어질 때 모든 동전을 앞면이 보이도록 놓을 수 있는지 판단하고, 가능하다면 그렇게 하기 위해 필요한 조작의 최소 횟수를 구하시오.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 10 000)
테스트 케이스의 첫 줄에는 동전의 개수 N이 주어진다. (1 ≤ N ≤ 1 000 000)
테스트 케이스의 둘째 줄에는 각 동전의 상태를 나타내는 길이 N의 문자열 S가 주어진다. 모든 1 ≤ i ≤ N에 대해, S의 i번째 문자는 i번째 동전이 앞면인 경우 H, 뒷면인 경우 T이다.
모든 테스트 케이스에 대한 N의 총합은 1 000 000을 넘지 않는다.
출력
각 테스트 케이스에 대해, 주어진 상태에서 모든 동전을 앞면이 보이도록 하기 위해 필요한 조작의 최소 횟수를 한 줄에 출력한다. 불가능하다면 −1을 대신 출력한다.