Jesting Jabberwocky
면접 대비시간 제한2초메모리 제한1024 MB
카드 무늬를 나타내는 문자열이 주어질 때 같은 무늬끼리 모이도록 옮겨야 하는 카드의 최소 개수를 구합니다.
문제
그림 J.1: 샘플 1에서 Alice는 손패를 정렬하려면 카드를 최소 두 장 옮겨야 한다.
유명한 카드 게임 제조사 Greatest Cards Production Company(GCPC)가 새 카드 게임 Jabberwocky를 출시했다. 이 게임에서는 모든 사람이 같은 장수의 카드를 받는데, 그 양이 꽤 많을 수도 있다. 각 카드는 하트, 다이아몬드, 클럽, 스페이드 중 한 무늬에 속한다.
Alice와 친구들은 요즘 모두가 이야기하는 이 카드 게임을 직접 해 보려고 들떠 있다. 교통 체증 때문에 Alice가 파티에 조금 늦었고, 친구들은 그녀를 초조하게 기다리고 있다. 친구들은 이미 카드를 모두 나눠 주었고, Alice만 빼고 모두 준비가 끝났다. Alice는 방금 자기 카드를 받았는데, 무늬별로 먼저 정렬하겠다고 고집한다. 그렇게 하려고 그녀는 손에서 카드 한 장을 골라 다른 자리에 끼워 넣는 일을 카드가 무늬별로 묶일 때까지 되풀이한다. 친구들은 Alice에게 점점 짜증을 내고 있고, 그녀는 가능한 한 빨리 카드를 정렬하고 싶어 한다. 게임을 시작하려면 Alice가 카드를 몇 장 옮겨야 할까?
입력
입력은 다음과 같이 주어진다.
- 한 줄에 문자열 ()가 주어진다. 이 문자열은 Alice가 처음 받았을 때의 카드 무늬 순서이다. 문자열은
h,d,c,s로만 이루어져 있으며, 각각 하트, 다이아몬드, 클럽, 스페이드를 뜻한다.
출력
무늬별로 카드를 정렬하기 위해 Alice가 옮겨야 하는 카드 수의 최솟값을 정수 하나로 출력한다.