연습문제 12-4

이번에도 다시 카 토크 퍼즐러다(http://www.cartalk.com/content/puzzlers).

한 번에 한 글자씩 제거해도 올바른 영어 단어가 되는 가장 긴 영어 단어는 무엇일까요?

이번에는 글자를 양쪽 끝이나 가운데에서 제거할 수 있지만, 문자들의 순서는 바꿀 수 없습니다. 글자를 제거해도 다시 영어 단어가 됩니다. 이렇게 하다 보면 결국에는 한 글자나 사전에서 발견할 수 없는 단어, 즉 영어 단어라고 할 수 없는 글자만 남게 됩니다. 이런 조건을 만족하는 가장 긴 단어는 무엇이고, 몇 글자로 되어 있는지 알고 싶습니다.

적당한 예시를 하나 보여드리겠습니다. Sprite. 괜찮나요? sprite로 시작해서 단어의 내부에서 문자 하나를 빼도 다른 단어가 됩니다. r을 제거해보면 단어 spite가 남습니다. 여기서 e를 제거하면 spit이 되고, s를 제거하면 pit이 되고, p를 제거하면 it, 마지막은 I가 됩니다.

이런 방법으로 줄일 수 있는 단어를 모두 찾고, 가장 긴 단어를 찾는 프로그램을 작성하라.

이 연습문제는 다른 연습문제보다 더 도전적인 문제이므로 여기 몇 가지 힌트를 제공하겠다.

1. 단어를 받아서 한 글자씩 제거하면서 단어가 되는 것을 모두 계산하려 할 것이다. 제거한 단어를 원래 단어의 “자식(children)”이라고 하자.

2. 재귀적으로 자식 중에도 줄일 수 있다(reducible)면 그 단어는 줄일 수 있다. 베이스 케이스로 빈 문자열도 줄일 수 있는 것으로 판단해야 한다.

3. 예제에 제공한 단어 목록 words.txt에는 한 글자 단어는 포함되어 있지 않다. 따라서 필요하다면 사전에 “I”, “a”, 빈 문자열을 추가해야 할 것이다.

4. 프로그램을 성능을 개선하고 싶다면 줄일 수 있다고 알려진 단어를 기록(memoize)하는 방법을 사용해야 한다.

해법: http://thinkpython2.com/code/reducible.py