문제
주연이는 "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+JnF1b3Q7T0smcXVvdDsgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDljIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWFjMTBcdWNkYjBcdWM5YzQgXHViMmU4XHVjNWI0XHVjNWQwXHVjMTFjIFx1Yzc3NCBcdWM1NGNcdWQzMGNcdWJjYjNcdWFjZmMgXHVjNzdjXHVjZTU4XHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NFx1Yzc3NCBcdWI0ZGNcdWI3ZWNcdWIwOWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkNjU0XHViYTc0XHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjA5YyBcdWIyZThcdWM1YjRcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YmNjMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiZxdW90O0xFRlQmcXVvdDsgXHViYzg0XHVkMmJjXHVjNzQ0IFx1YjIwNFx1Yjk3NFx1YmE3NCBcdWQ2NTRcdWJhNzRcdWM3NTggXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1Yzc3NFx1YzgwNCBcdWFjODNcdWM3M2NcdWI4NWMgXHViYzE0XHViMDEwXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBDXHViMjk0IEJcdWI4NWMgXHViNDE4XHVhY2UwIEFcdWIyOTQgWlx1Yjg1YyBcdWI0MWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiZxdW90O1JJR0hUJnF1b3Q7IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMDRcdWI5NzRcdWJhNzQgXHVkNjU0XHViYTc0XHVjNzU4IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWIyZTRcdWM3NGMgXHVhYzgzXHVjNzNjXHViODVjIFx1YmMxNFx1YjAxMFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgQlx1YjI5NCBDXHVhYzAwIFx1YjQxOFx1YWNlMCBaXHViMjk0IEFcdWFjMDAgXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzhmY1x1YzVmMFx1Yzc3NFx1YWMwMCBcdWJjODRcdWQyYmNcdWM3NDQgXHVhYzAwXHVjN2E1IFx1YzgwMVx1YWM4YyBcdWIyMGNcdWI3ZWNcdWMxMWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YjA1ZFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWFjZTAsIFx1YWRmOCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHViYzFkXHVkNjAwXHViMGI0XHVjNTdjIFx1ZDU2MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC4gKFx1YjJlOCwgXHVjODE1XHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMxY1x1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4pPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWMxMFx1Y2RiMFx1YzljNCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gXHViMmU4XHVjNWI0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMVx1Yzc3NFx1YWNlMCAxMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViYTcwLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwIFx1YjYxMFx1YjI5NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzU5MSBcdWIwNWRcdWM3NDAgXHVhY2Y1XHViYzMxXHVjNzc0IFx1YzU0NFx1YjJjOFx1YWNlMCwgXHVhY2Y1XHViYzMxXHVjNzQwIFx1Y2Q1Y1x1YjMwMCBcdWQ1NWMgXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWIwNWRcdWIwYjRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMGNcdWI3ZWNcdWM1N2MgXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YmM4NFx1ZDJiY1x1Yzc0NCBcdWIyMGNcdWI4MDBcdWM3NDQgXHViNTRjLCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHViYzFkXHVkNjAwXHVjOWMwXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzJkY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM1ZjBcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWJjODRcdWQyYmNcdWM3NDQgXHViMjA0XHViOTc0XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+UklHSFQsIE9LLCBMRUZUIDdcdWJjODgsIE9LLCBMRUZULCBPSywgTEVGVCAyXHViYzg4LCBPSywgTEVGVCAzXHViYzg4LCBPSzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzEyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZKRVx1MDE2MEFMQSIsImRlc2NyaXB0aW9uIjoiPHA+SXZpY2EgaXMgcGxheWluZyAmcXVvdDtIYW5nbWFuJnF1b3Q7IG9uIGhpcyBtb2JpbGUgcGhvbmUuIFRoZSBnb2FsIG9mIHRoZSBnYW1lIGlzIHRvIHVuY292ZXIgbGV0dGVycyBpbiBhIHNlY3JldCBwaHJhc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluaXRpYWxseSwgYWxsIGxldHRlcnMgaW4gdGhlIHNlY3JldCBwaHJhc2UgYXJlIG9ic2N1cmVkIGJ5IGRhc2hlcyAob25lIGZvciBlYWNoIGxldHRlcikuIEl2aWNhIGNob29zZXMgd2hpY2ggbGV0dGVyIHRvIHVuY292ZXIgbmV4dDsgaWYgdGhhdCBsZXR0ZXIgYXBwZWFycyBpbiB0aGUgc2VjcmV0IHBocmFzZSwgdGhlbiBhbGwgaXRzIG9jY3VycmVuY2VzIGFyZSByZXZlYWxlZC4gVGhlIGdhbWUgZW5kcyBhZnRlciBJdmljYSBndWVzc2VzIGFsbCB0aGUgbGV0dGVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SXZpY2EgcGxheXMgdGhpcyBnYW1lIGFsbCB0b28gb2Z0ZW4gYW5kIGhhcyBsZWFybmVkIHRvIHJlY29nbml6ZSBtYW55IG9mIHRoZSBwaHJhc2VzIGp1c3QgYnkgbG9va2luZyBhdCB0aGUgbGF5b3V0IG9mIHRoZSBkYXNoZXMuIFdoZW4gaGUgcmVjb2duaXplcyBhIHBocmFzZSwgSXZpY2Egd2FudHMgdG8gdHlwZSBpdCBpbiBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UbyBzZWxlY3QgdGhlIG5leHQgbGV0dGVyLCBJdmljYSB1c2VzIHRocmVlIGtleXM7IExFRlQsIFJJR0hUIGFuZCBPSy4mbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGV0dGVyIGlzIGFsd2F5cyBkaXNwbGF5ZWQgb24gc2NyZWVuLiBJbml0aWFsbHkgdGhpcyBpcyB0aGUgbGV0dGVyIEEuJm5ic3A7PFwvbGk+XHJcblx0PGxpPldoZW4gT0sgaXMgcHJlc3NlZCwgdGhlIGxldHRlciBkaXNwbGF5ZWQgaXMgc2VsZWN0ZWQgYW5kIGFsbCBpdHMgb2NjdXJyZW5jZXMgcmV2ZWFsZWQuIFRoZSBsZXR0ZXIgcmVtYWlucyBkaXNwbGF5ZWQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPldoZW4gTEVGVCBpcyBwcmVzc2VkLCB0aGUgcHJldmlvdXMgbGV0dGVyIGlzIGRpc3BsYXllZCAoZm9yIGV4YW1wbGUsIEMgYmVjb21lcyBCLCBaIGJlY29tZXMgQSkuJm5ic3A7PFwvbGk+XHJcblx0PGxpPldoZW4gUklHSFQgaXMgcHJlc3NlZCwgdGhlIG5leHQgbGV0dGVyIGlzIGRpc3BsYXllZCAoZm9yIGV4YW1wbGUsIEIgYmVjb21lcyBDLCBBIGJlY29tZXMgWikuJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGtleSBwcmVzc2VzIEl2aWNhIG5lZWRzIHRvIHJldmVhbCB0aGUgZW50aXJlIHBocmFzZSwgYW5kIG9uZSBwb3NzaWJsZSBvcmRlcmluZyBvZiBsZXR0ZXJzIGd1ZXNzZWQgdGhhdCBhY2hpZXZlcyB0aGUgc21hbGxlc3QgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgb3JkZXJpbmcgb2YgbGV0dGVycyBpcyBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgY29udGFpbnMgdGhlIHNlY3JldCBwaHJhc2UgJm5kYXNoOyBhdCBsZWFzdCAxIGFuZCBhdCBtb3N0IDEwMCBjaGFyYWN0ZXJzLiBBbGwgY2hhcmFjdGVycyB3aWxsIGJlIHVwcGVyY2FzZSBsZXR0ZXJzIG9yIHNwYWNlcy4gVGhlIHBocmFzZSBzdGFydHMgYW5kIGVuZHMgaW4gYSBsZXR0ZXIsIGFuZCB0aGVyZSBpcyBleGFjdGx5IG9uZSBzcGFjZSBiZXR3ZWVuIHdvcmRzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lLCBvdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBrZXkgcHJlc3NlcyBuZWVkZWQgdG8gcmV2ZWFsIHRoZSBlbnRpcmUgcGhyYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGxpbmUsIG91dHB1dCBhbiBvcmRlcmluZyB3aGljaCBhY2hpZXZlcyB0aGF0IHNtYWxsZXN0IG51bWJlci4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+SW4gdGhlIGV4YW1wbGUsIEl2aWNhIGNhbiBwcmVzcyBrZXlzIGluIHRoaXMgb3JkZXI6IFJJR0hULCBPSywgTEVGVCA3IHRpbWVzLCBPSywgTEVGVCwgT0ssIExFRlQgMiB0aW1lcywgT0ssIExFRlQgMyB0aW1lcywgT0suPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=
