PC/UVa ID : 110307/10150

이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • firefox4 b9
  • eclipse 3.6.1 + vrapper
  • lua 5.1.4

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 23, Doublets, page 105)

참고 링크

이야기

더블릿은 딱 한글자만 다른 한쌍의 단어를 뜻한다. 예를 들어 booster 와 rooster, rooster 와 roaster 이다.

총 25143개의 단어를 담은 사전이 주어질 때, 사용자가 요구한 두 단어 사이의 더블릿들을 출력하라.

프로그램의 입/출력

  1. 프로그램은 최초로 사전의 단어들을 입력 받는다.
  2. 사전의 단어들을 입력 받는 중 공백이 입력 되면, 사전 입력을 중단한다.

  3. 그리고 더블릿을 찾을 시작 단어와 끝 단어, 두개를 입력 받는다.
  4. 그리고 그 두 단어 사이의 더블릿을 모두 출력 한다.
  5. 4번이 끝났다면, 3번 부타 다시 반복 한다.

예외 상황

  • 각 더블릿 사이의 출력은 제일 짦은 시퀀스를 갖는 더블릿을 출력 하라.
    예) rooster 의 더블릿은 booster, roaster 가 있는데, 이중 booster가 더 짤음 시퀸스를 갖는다고 본다.

  • 가장 짦은 스퀸스가 여러개라면, 아무거나 출력하라.
  • 답이 없을 경우, No solution 을 출력 하라
  • 각 케이스 사이에는 빈 줄을 넣는다.

맛보기 코드

맛보기 사진

여담

  • 깔끔한 코드가 나오지 않아, 10일 넘겨 쉬었다. :)

  • 그래프 검색 알고리즘에 여러 종류가 있는 것을 알았고, 그 중에 BFS 라는 이름을 알았다.
    - 사실 알고리즘의 경우, 기존에 쓰고는 있었지만, 어떤 이름으로 세상에서 불리는지 모르는 경우가 많다.

  • 난 사전을 미리 노드 구조로 만들고, 그 노드를 이용하여, 인접한 더블릿 중 스퀸스가 짦은 더블릿을 찾아, 끝 단어까지 쫒아갔다.

:wq

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요

  1. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2011.01.23 01:36 신고  Addr  Edit/Del  Reply

    문제 24번 꽤 어렵네. fmt 구현인데 아이디어가 떠오르지 않는다. :)

  2. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2011.01.25 02:07 신고  Addr  Edit/Del  Reply

    24번 문제 풀었는데, if문이 10개 정도 깔리니, 보기 싫다.