3128번 - Hangman Game 스페셜 저지

주연이는 "Hangman"이라 불리는 게임을 하고 있다. 이 게임의 목표는 감춰진 알파벳을 모두 맞히는 게임이다.

맨 처음에 주연이가 맞춰야 할 단어의 각 알파벳은 '-'로 가려져있다. 그러면 주연이는 알파벳 하나를 고른다. 만약 그 알파벳이 단어에 포함되어 있다면 그 알파벳에 해당하는 모든 단어가 드러난다. 주연이가 모든 알파벳을 맞히면 게임은 끝난다.

주연이는 워낙 고수라 알파벳의 개수만 보고도 단어를 맞출 수 있다. 주연이는 가능한 한 빨리 게임을 끝내고 싶어한다.

단어를 선택하기 위해 주연이는 LEFT, RIGHT, OK라는 3개의 버튼을 사용한다

• 화면에는 항상 한 개의 알파벳이 보여진다. 맨 처음에 보여지는 알파벳은 'A'이다.
• "OK" 버튼을 누르면 화면에 나타난 단어를 선택하게 되고, 감춰진 단어에서 이 알파벳과 일치하는 부분이 드러난다. 이 때, 화면에 나타난 단어의 상태는 변하지 않는다.
• "LEFT" 버튼을 누르면 화면의 알파벳이 이전 것으로 바뀐다. 예를 들어, C는 B로 되고 A는 Z로 된다.
• "RIGHT" 버튼을 누르면 화면의 알파벳이 다음 것으로 바뀐다. 예를 들어, B는 C가 되고 Z는 A가 된다.

주연이가 버튼을 가장 적게 눌러서 게임을 끝낼 수 있는 방법을 알아내고, 그 방법으로 밝혀내야 할 알파벳의 순서를 출력하시오. (단, 정답이 여러개가 있다면 그 중 아무거나 출력하면 된다.)

첫 줄에 감춰진 단어가 입력으로 들어온다. 단어의 길이는 1 이상이고 100 이하이며, 알파벳 대문자 또는 공백으로 이루어져있다. 또한 단어의 양 끝은 공백이 아니고, 공백은 최대 한 개가 있다.

첫 줄에 게임을 끝내기 위해 버튼을 눌러야 하는 최소 횟수를 출력하시오.

두 번째 줄에는 위의 방법으로 버튼을 눌렀을 때, 알파벳을 밝혀지는 순서대로 출력하시오.

예시에서 주연이는 다음의 순서로 버튼을 누르면 된다.

RIGHT, OK, LEFT 7번, OK, LEFT, OK, LEFT 2번, OK, LEFT 3번, OK