2012/09/13 15:37

코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이

  <- 이 책에 나오는 문제라고 합니다.

문제 출처는 다음 링크입니다.
http://www.insightbook.co.kr/post/3917 

『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.
심화문제 2: 가장 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

 이 문제는 사전상의 각 단어를 노드, 변환가능한 단어쌍을 링크로 놓으면 그래프에서의 경로찾기 문제로 치환할 수 있습니다.  

여기서는 A* 알고리즘을 써서 구현했습니다. A*알고리즘에서는 현재 위치가 목표와 얼마나 가까운지 예측하는 게 필요한데, 글자 하나 다를 때 한 번만에 옮겨갈 수 있다고 보수적인 추정을 사용하면 시간을 약간 더 걸리지만 최소 경로를 찾아낼 수 있습니다. 

최대 경로, 즉 가장 많은 수의 단어를 쓰는 경우는 변환을 한 번 할 때 weight을 -1로 둬서 가장 많은 변환을 하도록 해 주면 찾을 수 있습니다. 

 실행결과:

(damp -> like):(5)[damp, dame, dime, dike, like]

(start -> final):(13)[start, stare, stave, seave, serve, serie, ferie, ferae, feral, fetal, fatal, fanal, final]

(china -> japan):(15)[china, chine, shine, seine, seise, sense, mense, manse, manie, matie, matin, satin, satan, sapan, japan]

(damp -> like):(2734)[]  <-- 결과는 longest.txt 에 올려놨습니다.

찾아보니 다른 분이 더 긴 longest 결과를 찾으셨네요 ^^; 제 건 부정확한 듯. 좀 더 고쳐보겠습니다. 


package insightbook.event.last;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.FileSystem;
import java.nio.file.FileSystems;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Set;

public class WordTransform {

private final Map<String, Collection<String>> link;

private WordTransform(Map<String, Collection<String>> link) {
this.link = link;
}

public static Builder getBuilder() {
return new Builder();
}

public Collection<String> getTransformableWords(String word) {
return link.get(word);
}


public List<String> findPath(String start, String goal) {
return findPath(start, goal, 1);
}

public List<String> findLongestPath(String start, String goal) {
return findPath(start, goal, -1);
}

public List<String> findPath(String start, String goal, int weightPerTransform) {

// Cost from start along best known path.
final Map<String, Integer> gScore = new HashMap<>();
gScore.put(start, 0);

// Estimated total cost from start to goal through y.
final Map<String, Integer> fScore = new HashMap<>();
fScore.put(start, huristicCostEstimate(start, goal, weightPerTransform));

// The set of nodes already evaluated.
Set<String> closedSet = new HashSet<>();

// The set of tentative nodes to be evaluated,
// initially containing the start node
Set<String> openSet = new HashSet<>();
openSet.add(start);

// Priority Queue for picking up least fScore
final int INITIAL_CAPACITY = 11;
PriorityQueue<String> queue = new PriorityQueue<String>(
INITIAL_CAPACITY, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
int diff = fScore.get(o1) - fScore.get(o2);
return (diff!=0)? diff : o1.compareTo(o2);
}
});
queue.add(start);

// The map of navigated nodes.
Map<String, String> cameFrom = new HashMap<>();

while (!queue.isEmpty()) {
String current = queue.poll();
openSet.remove(current);
// System.out.println(fScore.get(current)+":"+constructPath(cameFrom, current));
if (goal.equals(current)) {
// System.out.println("count: "+closedSet.size());
return constructPath(cameFrom, current);
}
closedSet.add(current);

int tentativeGScore = gScore.get(current) + weightPerTransform;
Collection<String> ns = getTransformableWords(current);
if (ns==null) continue;
for (String neighbor : ns) {
if (closedSet.contains(neighbor))
continue;
if (!openSet.contains(neighbor)
|| tentativeGScore < gScore.get(neighbor)) {

cameFrom.put(neighbor, current);
gScore.put(neighbor, tentativeGScore);
fScore.put(neighbor, gScore.get(neighbor)
+ huristicCostEstimate(neighbor, goal, weightPerTransform));

if (!openSet.contains(neighbor))
openSet.add(neighbor);
queue.add(neighbor);
}
}
}

return null;
}

private List<String> constructPath(Map<String, String> cameFrom, String current) {

List<String> path = (cameFrom.containsKey(current)) ?
constructPath(cameFrom, cameFrom.get(current)) : new LinkedList<String>();
path.add(current);
return path;
}

private int huristicCostEstimate(String start, String goal, int multiplyCoeff) {

int estimate = 0;

for (int i = 0; i < Math.min(start.length(), goal.length()); i++) {
if (start.charAt(i) != goal.charAt(i))
estimate++;
}

return estimate * multiplyCoeff;
}

static String[] getMasks(String s) {

String[] masks = new String[s.length()];
for (int i = 0; i < s.length(); i++) {
masks[i] = s.substring(0, i) + "*" + s.substring(i + 1, s.length());
}

return masks;
}

public static class Builder {

private Map<String, Set<String>> maskSet = new HashMap<>();

public Builder load(String word) {

String[] masks = getMasks(word);
for (String mask : masks) {
if (!maskSet.containsKey(mask))
maskSet.put(mask, new HashSet<String>());
maskSet.get(mask).add(word);
}

return this;
}

public Builder load(Path path) {
try (BufferedReader reader = Files.newBufferedReader(path,
StandardCharsets.UTF_8);) {

for (String line = reader.readLine(); line != null; line = reader
.readLine()) {
load(line);
}

} catch (IOException e) {
e.printStackTrace();
}
return this;
}

public WordTransform build() {

Map<String, Collection<String>> link = new HashMap<>();

for (Entry<String, Set<String>> e : maskSet.entrySet()) {
if (e.getValue().size() > 1) {
Set<String> set = e.getValue();
for (String word : set) {
if (!link.containsKey(word))
link.put(word, new HashSet<String>());
link.get(word).addAll(getRelativeComplement(word, set));
}
}
}

return new WordTransform(link);
}

private static Collection<? extends String> getRelativeComplement(
String word, Set<String> set) {
Set<String> rc = new HashSet<>(set);
rc.remove(word);
return rc;
}

}

public void printPath(String start, String goal) {

List<String> path = findPath(start, goal);
System.out.printf("(%s -> %s):(%d)%s\n", start, goal, (path==null)?-1:path.size(), path);
}

public void printLongestPath(String start, String goal) {

List<String> path = findLongestPath(start, goal);
System.out.printf("(%s -> %s):(%d)%s\n", start, goal, (path==null)?-1:path.size(), path);
}

public static void main(String[] args) {

FileSystem fs = FileSystems.getDefault();
Path path4 = fs.getPath("word4.txt");
Path path5 = fs.getPath("word5.txt");
WordTransform t = WordTransform.getBuilder().load(path4).load(path5).build();

t.printPath("damp", "like");
t.printPath("start", "final");
t.printPath("china", "japan");

t.printLongestPath("damp", "like");
}

}

덧글

  • 히언 2012/09/19 17:19 # 답글

    오, 역시 머리쓰기의 달인이셨군요!!!
  • 성큼이 2012/09/20 23:25 #

    ㅋㅋ 달인은 좀 많이 아닌 것 같지만 퍼즐풀이 같은건 즐기는 편입죠 ^^;
  • 앙탈 2012/11/04 19:50 # 답글

    성큼형님 저 한달남았어여 ㅠㅠ

    잘지내시나여
  • 성큼이 2012/11/08 14:17 #

    ㅎㅎ 잘 지내요 몸조심하고 무사히 전역해요
  • David 2017/11/25 12:46 # 삭제 답글

    Hi, Neat post. There's a problem with your site in internet explorer, would test this IE still is the market leader and a good portion of people will miss your excellent writing because of this problem.
  • Daniel 2017/12/02 09:05 # 삭제 답글

    Enjoyed examining this, very good stuff, thankyou. Talk sense to a fool and he calls you foolish. by Euripides.
  • Richard 2017/12/04 20:15 # 삭제 답글

    How significantly of an special post, keep on posting much better half
  • Joseph 2017/12/06 09:19 # 삭제 답글

    I got what you intend, thankyou for putting up.Woh I am lucky to find this website through google. Being intelligent is not a felony, but most societies evaluate it as at least a misdemeanor. by Lazarus Long.
  • Joseph 2017/12/08 22:10 # 삭제 답글

    Today, while I was at work, my sister stole my apple ipad and tested to see if it can survive a 30 foot drop, just so she can be a youtube sensation. My apple ipad is now destroyed and she has 83 views. I know this is entirely off topic but I had to share it with someone!
  • Paul 2017/12/12 09:43 # 삭제 답글

    Wow, marvelous blog structure! How long have you been running a blog
  • Michael 2017/12/14 00:49 # 삭제 답글

    Hey, thanks for the blog article.Really looking forward to read more. Much obliged.
  • William 2017/12/20 12:14 # 삭제 답글

    Very efficiently written post. It will be valuable to anyone who usess it, as well as myself. Keep doing what you are doing i will definitely read more posts.
  • James 2017/12/23 00:05 # 삭제 답글

    Hello to every one, its truly a fastidious for me to visit this site, it contains helpful Information.
  • Thomas 2017/12/26 08:55 # 삭제 답글

    I like what you guys tend to be up too. Such clever work and coverage! Keep up the very good works guys I've incorporated you guys to my personal blogroll.
  • Thomas 2017/12/26 23:11 # 삭제 답글

    Article Source a viral game app is not that much difficult.
  • Joseph 2017/12/31 23:35 # 삭제 답글

    Hey there! Do you know if they make any plugins to help with Search Engine Optimization? I'm trying to get my blog to rank for some targeted keywords but I'm not seeing very good results. If you know of any please share. Thank you!
  • Donald 2018/01/06 10:15 # 삭제 답글

    I got what you intend, thankyou for putting up.Woh I am lucky to find this website through google. Being intelligent is not a felony, but most societies evaluate it as at least a misdemeanor. by Lazarus Long.
  • John 2018/01/08 10:43 # 삭제 답글

    Thank you for every other informative blog. The place else may just I get that type of info written in such a perfect means? I've a project that I'm just now working on, and I have been at the glance out for such information.
댓글 입력 영역