책 정리하기
면접 대비시간 제한1초메모리 제한1024 MB
L, M, S 문자로 이루어진 문자열이 주어질 때, 모든 L이 앞에, 그다음 M, 마지막에 S가 오도록 두 문자를 교환하는 최소 횟수를 구한다.
문제
Valentina는 책장의 책을 특정한 방식으로 정리하려고 한다. 책장을 볼 때마다 큰 책이 모두 왼쪽에, 그다음 중간 크기 책이 모두, 마지막으로 작은 책이 모두 오른쪽에 오도록 책을 다시 배치한다. 이때 임의의 두 책을 골라 위치를 맞바꾸는 작업을 반복한다. 두 책의 위치를 맞바꾸는 것을 스왑이라고 한다.
Valentina가 책장의 책을 원하는 대로 정리하는 데 필요한 최소 스왑 횟수를 구하시오.
입력
입력은 정확히 한 줄이며, 길이가 최대 500 000인 문자열이 주어진다. 각 문자는 L, M, S 중 하나이다.
출력
모든 L이 먼저 나오고, 그다음 모든 M이 나오고, 마지막으로 모든 S가 나오도록 책을 정리하는 데 필요한 최소 스왑 횟수를 정수로 출력한다.