페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5468

무로 바꾸기 (Moo Operations) 1초 128MB

문제

소영이는 심심해서 'M' 문자와 'O' 문자로만 이루어진 문자열을 "MOO"라는 문자열로 바꾸려고 한다.

총 Q개의 바꿀 문자열이 주어지면, 최소 몇 번의 변경을 통해 "MOO"로 바꾸는게 가능한지 알아보자.

변경의 방법은 아래와 같이 두 가지 방법이 있다.

  1. 문자열의 첫 번째 문자 혹은 마지막 문자를 반대로 바꾼다.

    • 'M'이면 'O'가 되고, 'O'면 'M'이 된다.

  2. 문자열의 첫 번째 문자 혹은 마지막 문자를 삭제한다.

만약 "MOO"로 바꾸는게 불가능하다면 "-1"을 출력하자.


입력

첫 줄에 Q가 주어진다. (1≤Q≤100)

이어 Q줄에 걸쳐 'M'과 'O'로만 이루어진 문자열이 주어진다. 해당 문자열의 길이는 1이상 100이하이다.


출력

각 줄에 해당 문자열을 "MOO"로 바꾸기 위한 최소 변경 횟수를 출력하며, 불가능한 경우에는 -1을 출력한다.


예제1

입력
3

MOMMOM

MMO

MOO
출력
4

-1

0

첫 번째 문자열을 "MOO"로 바꾸기 위해서는 네 번의 변경이 필요하다.

  1. 마지막 문자를 'O'로 바꾼다.

  2. 첫 번째 문자를 삭제한다.

  3. 첫 번째 문자를 삭제한다.

  4. 첫 번째 문자를 삭제한다.

두 번째 문자열은 "MOO"로 바꾸는 것이 불가능하다.

세 번째 문자열은 이미 "MOO"다.


출처

USACO 2023 January Bronze

역링크 공식 문제집만