문제 23, 더플릿, Doublets, PC/UVa ID : 110307/10150

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)
  

참고 링크

• http://www.lua.org/manual/5.1/manual.html  - 루아 메뉴얼, 스트링 찾을려고
  
• http://online-judge.uva.es/p/v101/10150.html - 원문

이야기

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

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

프로그램의 입/출력

1. 프로그램은 최초로 사전의 단어들을 입력 받는다.
   
2. 사전의 단어들을 입력 받는 중 공백이 입력 되면, 사전 입력을 중단한다.
   
   
3. 그리고 더블릿을 찾을 시작 단어와 끝 단어, 두개를 입력 받는다.
   
4. 그리고 그 두 단어 사이의 더블릿을 모두 출력 한다.
   
5. 4번이 끝났다면, 3번 부타 다시 반복 한다.
   

예외 상황

• 각 더블릿 사이의 출력은 제일 짦은 시퀀스를 갖는 더블릿을 출력 하라.
  예) rooster 의 더블릿은 booster, roaster 가 있는데, 이중 booster가 더 짤음 시퀸스를 갖는다고 본다.
  
  
• 가장 짦은 스퀸스가 여러개라면, 아무거나 출력하라.
  
• 답이 없을 경우, No solution 을 출력 하라
  
• 각 케이스 사이에는 빈 줄을 넣는다.
  

맛보기 코드
-- Doublets -- PC/UVa : 110307/10150 -- http://ikpil.com -- 2011.01.08 ------------------------------------------------------------------------------- function fn_doublets_set_node(tb_dic) for w1, node1 in pairs(tb_dic) do for w2, node2 in pairs(tb_dic) do local fn1, fn2 = string.gmatch(w1, "%a"), string.gmatch(w2, "%a") local bit1, bit2, diff, diff_point, begin = fn1(), fn2(), 0, 1, 1 while nil ~= bit1 or nil ~= bit2 do if bit1 ~= bit2 then diff = diff + 1 diff_point = begin end bit1, bit2, begin = fn1(), fn2(), begin + 1 end if 1 == diff then if nil == node1[w2] then node1[#node1 + 1] = { doublet=w2, order=diff_point } node1[w2] = diff_point end if nil == node2[w1] then node2[#node2 + 1] = { doublet=w1, order=diff_point } node2[w1] = diff_point end end end table.sort(node1, function (a, b) return a.order < b.order end) end --[[ print("debug code ----------------------------------------") for w1, node in pairs(tb_dic) do print(string.format("%s doublets", w1)) for i = 1, #node do print(node[i].doublet, node[i].order) end end print("debug code ----------------------------------------") io.flush() --]] end function fn_doublets_input_find_doublet() local words = io.read("*line") local tb_word = {} for word in string.gmatch(words, "%a+") do table.insert(tb_word, word) end if 2 > #tb_word then return nil end return tb_word[1], tb_word[2] end function fn_doublets_bfs(tb_dic, bword, eword) local tb_sequence = {} while true do if nil == tb_sequence[bword] then tb_sequence[#tb_sequence + 1] = bword tb_sequence[bword] = true end -- when last word, break if bword == eword then break end local tb_doublet = tb_dic[bword] -- when no doublet, break if nil == tb_doublet or 0 == #tb_doublet then break end -- find doublet local fdoublet = nil for i = 1, #tb_doublet do if nil == tb_sequence[tb_doublet[i].doublet] then fdoublet = tb_doublet[i].doublet --[[ debug code print(tb_doublet[i].doublet, "debug"); io.flush() --]] break end end -- when can't find doublet, break if nil == fdoublet then break end -- bword next bword = fdoublet end -- when can't find eword, return nil if true ~= tb_sequence[eword] then return nil end return tb_sequence end function main() local tb_dic = {} while true do local w = io.read("*line") if nil == w or "" == w then break end tb_dic[w] = tb_dic[w] or {} end fn_doublets_set_node(tb_dic) while true do local bword, eword = fn_doublets_input_find_doublet() if nil == bword then break end local tb_doublets = fn_doublets_bfs(tb_dic, bword, eword) if nil == tb_doublets then print("No solution.") else for i = 1, #tb_doublets do print(tb_doublets[i]) end end print(); io.flush() end end main()

맛보기 사진

여담

• 깔끔한 코드가 나오지 않아, 10일 넘겨 쉬었다. :)
  
  
• 그래프 검색 알고리즘에 여러 종류가 있는 것을 알았고, 그 중에 BFS 라는 이름을 알았다.
  - 사실 알고리즘의 경우, 기존에 쓰고는 있었지만, 어떤 이름으로 세상에서 불리는지 모르는 경우가 많다.
  
  
• 난 사전을 미리 노드 구조로 만들고, 그 노드를 이용하여, 인접한 더블릿 중 스퀸스가 짦은 더블릿을 찾아, 끝 단어까지 쫒아갔다.
  

:wq