문제
주연이는 "Hangman"이라 불리는 게임을 하고 있다. 이 게임의 목표는 감춰진 알파벳을 모두 맞히는 게임이다.
맨 처음에 주연이가 맞춰야 할 단어의 각 알파벳은 '-'로 가려져있다. 그러면 주연이는 알파벳 하나를 고른다. 만약 그 알파벳이 단어에 포함되어 있다면 그 알파벳에 해당하는 모든 단어가 드러난다. 주연이가 모든 알파벳을 맞히면 게임은 끝난다.
주연이는 워낙 고수라 알파벳의 개수만 보고도 단어를 맞출 수 있다. 주연이는 가능한 한 빨리 게임을 끝내고 싶어한다.
단어를 선택하기 위해 주연이는 LEFT, RIGHT, OK라는 3개의 버튼을 사용한다
- 화면에는 항상 한 개의 알파벳이 보여진다. 맨 처음에 보여지는 알파벳은 'A'이다.
- "OK" 버튼을 누르면 화면에 나타난 단어를 선택하게 되고, 감춰진 단어에서 이 알파벳과 일치하는 부분이 드러난다. 이 때, 화면에 나타난 단어의 상태는 변하지 않는다.
- "LEFT" 버튼을 누르면 화면의 알파벳이 이전 것으로 바뀐다. 예를 들어, C는 B로 되고 A는 Z로 된다.
- "RIGHT" 버튼을 누르면 화면의 알파벳이 다음 것으로 바뀐다. 예를 들어, B는 C가 되고 Z는 A가 된다.
주연이가 버튼을 가장 적게 눌러서 게임을 끝낼 수 있는 방법을 알아내고, 그 방법으로 밝혀내야 할 알파벳의 순서를 출력하시오. (단, 정답이 여러개가 있다면 그 중 아무거나 출력하면 된다.)
출력
첫 줄에 게임을 끝내기 위해 버튼을 눌러야 하는 최소 횟수를 출력하시오.
두 번째 줄에는 위의 방법으로 버튼을 눌렀을 때, 알파벳을 밝혀지는 순서대로 출력하시오.
힌트
예시에서 주연이는 다음의 순서로 버튼을 누르면 된다.
RIGHT, OK, LEFT 7번, OK, LEFT, OK, LEFT 2번, OK, LEFT 3번, OK
W3sicHJvYmxlbV9pZCI6IjMxMjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJIYW5nbWFuIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzhmY1x1YzVmMFx1Yzc3NFx1YjI5NCAmcXVvdDtIYW5nbWFuJnF1b3Q7XHVjNzc0XHViNzdjIFx1YmQ4OFx1YjlhY1x1YjI5NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc1OCBcdWJhYTlcdWQ0NWNcdWIyOTQgXHVhYzEwXHVjZGIwXHVjOWM0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWRlXHVkNzg4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWFjMDAgXHViOWRlXHVjZGIwXHVjNTdjIFx1ZDU2MCBcdWIyZThcdWM1YjRcdWM3NTggXHVhYzAxIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCAmIzM5Oy0mIzM5O1x1Yjg1YyBcdWFjMDBcdWI4MjRcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YmE3NCBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFkZjggXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1YjJlOFx1YzViNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViYTc0IFx1YWRmOCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjRcdWFjMDAgXHViNGRjXHViN2VjXHViMDljXHViMmU0LiBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWFjMDAgXHViYWE4XHViNGUwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWI5ZGVcdWQ3ODhcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWYwXHVjNzc0XHViMjk0IFx1YzZjY1x1YjA5OSBcdWFjZTBcdWMyMThcdWI3N2MgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjljYyBcdWJjZjRcdWFjZTBcdWIzYzQgXHViMmU4XHVjNWI0XHViOTdjIFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWJlNjhcdWI5YWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzhmY1x1YzVmMFx1Yzc3NFx1YjI5NCBMRUZULCBSSUdIVCwgT0tcdWI3N2NcdWIyOTQgM1x1YWMxY1x1Yzc1OCBcdWJjODRcdWQyYmNcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVkNjU0XHViYTc0XHVjNWQwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWJjZjRcdWM1ZWNcdWM5YzRcdWIyZTQuIFx1YjllOCBcdWNjOThcdWM3NGNcdWM1ZDAgXHViY2Y0XHVjNWVjXHVjOWMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCAmIzM5O0EmIzM5O1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+JnF1b3Q7T0smcXVvdDsgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDljIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWFjMTBcdWNkYjBcdWM5YzQgXHViMmU4XHVjNWI0XHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWFjZmMgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWI0ZGNcdWI3ZWNcdWIwOWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWIwOThcdWQwYzBcdWIwOWMgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWJjYzBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mcXVvdDtMRUZUJnF1b3Q7IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHVkNjU0XHViYTc0XHVjNzU4IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWM3NzRcdWM4MDQgXHVhYzgzXHVjNzNjXHViODVjIFx1YmMxNFx1YjAxMFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQ1x1YjI5NCBCXHViODVjIFx1YjQxOFx1YWNlMCBBXHViMjk0IFpcdWI4NWMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mcXVvdDtSSUdIVCZxdW90OyBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0IFx1ZDY1NFx1YmE3NFx1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHViMmU0XHVjNzRjIFx1YWM4M1x1YzczY1x1Yjg1YyBcdWJjMTRcdWIwMTBcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIEJcdWIyOTQgQ1x1YWMwMCBcdWI0MThcdWFjZTAgWlx1YjI5NCBBXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4ZmNcdWM1ZjBcdWM3NzRcdWFjMDAgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHViMjBjXHViN2VjXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWIwNWRcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHVhY2UwLCBcdWFkZjggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YmMxZFx1ZDYwMFx1YjBiNFx1YzU3YyBcdWQ1NjAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWIyZTgsIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMWNcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0IFx1YWRmOCBcdWM5MTEgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjMTBcdWNkYjBcdWM5YzQgXHViMmU4XHVjNWI0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMSBcdWM3NzRcdWMwYzFcdWM3NzRcdWFjZTAgMTAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YmE3MCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MCBcdWI2MTBcdWIyOTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjNzQwIFx1YWNmNVx1YmMzMVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWFjZTAsIFx1YWNmNVx1YmMzMVx1Yzc0MCBcdWNkNWNcdWIzMDAgXHVkNTVjIFx1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHViMDVkXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViN2VjXHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjBjXHViODAwXHVjNzQ0IFx1YjU0YywgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YmMxZFx1ZDYwMFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWYwXHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWI4NWMgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlJJR0hULCBPSywgTEVGVCA3XHViYzg4LCBPSywgTEVGVCwgT0ssIExFRlQgMlx1YmM4OCwgT0ssIExFRlQgM1x1YmM4OCwgT0s8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMjgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWSkVcdTAxNjBBTEEiLCJkZXNjcmlwdGlvbiI6IjxwPkl2aWNhIGlzIHBsYXlpbmcgJnF1b3Q7SGFuZ21hbiZxdW90OyBvbiBoaXMgbW9iaWxlIHBob25lLiBUaGUgZ29hbCBvZiB0aGUgZ2FtZSBpcyB0byB1bmNvdmVyIGxldHRlcnMgaW4gYSBzZWNyZXQgcGhyYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Jbml0aWFsbHksIGFsbCBsZXR0ZXJzIGluIHRoZSBzZWNyZXQgcGhyYXNlIGFyZSBvYnNjdXJlZCBieSBkYXNoZXMgKG9uZSBmb3IgZWFjaCBsZXR0ZXIpLiBJdmljYSBjaG9vc2VzIHdoaWNoIGxldHRlciB0byB1bmNvdmVyIG5leHQ7IGlmIHRoYXQgbGV0dGVyIGFwcGVhcnMgaW4gdGhlIHNlY3JldCBwaHJhc2UsIHRoZW4gYWxsIGl0cyBvY2N1cnJlbmNlcyBhcmUgcmV2ZWFsZWQuIFRoZSBnYW1lIGVuZHMgYWZ0ZXIgSXZpY2EgZ3Vlc3NlcyBhbGwgdGhlIGxldHRlcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkl2aWNhIHBsYXlzIHRoaXMgZ2FtZSBhbGwgdG9vIG9mdGVuIGFuZCBoYXMgbGVhcm5lZCB0byByZWNvZ25pemUgbWFueSBvZiB0aGUgcGhyYXNlcyBqdXN0IGJ5IGxvb2tpbmcgYXQgdGhlIGxheW91dCBvZiB0aGUgZGFzaGVzLiBXaGVuIGhlIHJlY29nbml6ZXMgYSBwaHJhc2UsIEl2aWNhIHdhbnRzIHRvIHR5cGUgaXQgaW4gYXMgcXVpY2tseSBhcyBwb3NzaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VG8gc2VsZWN0IHRoZSBuZXh0IGxldHRlciwgSXZpY2EgdXNlcyB0aHJlZSBrZXlzOyBMRUZULCBSSUdIVCBhbmQgT0suJm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxldHRlciBpcyBhbHdheXMgZGlzcGxheWVkIG9uIHNjcmVlbi4gSW5pdGlhbGx5IHRoaXMgaXMgdGhlIGxldHRlciBBLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5XaGVuIE9LIGlzIHByZXNzZWQsIHRoZSBsZXR0ZXIgZGlzcGxheWVkIGlzIHNlbGVjdGVkIGFuZCBhbGwgaXRzIG9jY3VycmVuY2VzIHJldmVhbGVkLiBUaGUgbGV0dGVyIHJlbWFpbnMgZGlzcGxheWVkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5XaGVuIExFRlQgaXMgcHJlc3NlZCwgdGhlIHByZXZpb3VzIGxldHRlciBpcyBkaXNwbGF5ZWQgKGZvciBleGFtcGxlLCBDIGJlY29tZXMgQiwgWiBiZWNvbWVzIEEpLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5XaGVuIFJJR0hUIGlzIHByZXNzZWQsIHRoZSBuZXh0IGxldHRlciBpcyBkaXNwbGF5ZWQgKGZvciBleGFtcGxlLCBCIGJlY29tZXMgQywgQSBiZWNvbWVzIFopLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBrZXkgcHJlc3NlcyBJdmljYSBuZWVkcyB0byByZXZlYWwgdGhlIGVudGlyZSBwaHJhc2UsIGFuZCBvbmUgcG9zc2libGUgb3JkZXJpbmcgb2YgbGV0dGVycyBndWVzc2VkIHRoYXQgYWNoaWV2ZXMgdGhlIHNtYWxsZXN0IG51bWJlci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIG9yZGVyaW5nIG9mIGxldHRlcnMgaXMgbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIGNvbnRhaW5zIHRoZSBzZWNyZXQgcGhyYXNlICZuZGFzaDsgYXQgbGVhc3QgMSBhbmQgYXQgbW9zdCAxMDAgY2hhcmFjdGVycy4gQWxsIGNoYXJhY3RlcnMgd2lsbCBiZSB1cHBlcmNhc2UgbGV0dGVycyBvciBzcGFjZXMuIFRoZSBwaHJhc2Ugc3RhcnRzIGFuZCBlbmRzIGluIGEgbGV0dGVyLCBhbmQgdGhlcmUgaXMgZXhhY3RseSBvbmUgc3BhY2UgYmV0d2VlbiB3b3Jkcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSwgb3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2Yga2V5IHByZXNzZXMgbmVlZGVkIHRvIHJldmVhbCB0aGUgZW50aXJlIHBocmFzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lLCBvdXRwdXQgYW4gb3JkZXJpbmcgd2hpY2ggYWNoaWV2ZXMgdGhhdCBzbWFsbGVzdCBudW1iZXIuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBleGFtcGxlLCBJdmljYSBjYW4gcHJlc3Mga2V5cyBpbiB0aGlzIG9yZGVyOiBSSUdIVCwgT0ssIExFRlQgNyB0aW1lcywgT0ssIExFRlQsIE9LLCBMRUZUIDIgdGltZXMsIE9LLCBMRUZUIDMgdGltZXMsIE9LLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d
