[알고리즘-공부] 최소편집거리-알고리즘시간 과제2

문제의 출처는 교수님께서 주신 것입니다.

문제 :  5.3최소 편집 거리 문제_Java(류관희교수).docx

과제 : 편집거리 추적부분을 매트릭스로 표현한 자바 코드 짜오기

코드 :

 

public class Main {
	public int M[][] = new int[100][100];

	public int getMin(int a, int b, int c) {
		int min = a;
		if (min > b)
			min = b;
		if (min > c)
			min = c;
		return min;
	}

	public int getDistance(String a, String b) {
		for (int i = 0; i < a.length(); i++) {
			M[i][0] = i;
		}
		for (int j = 0; j < b.length(); j++) {
			M[0][j] = j;
		}
		for (int i = 1; i < a.length(); i++) {
			for (int j = 1; j < b.length(); j++) {
				if (a.charAt(i) == b.charAt(j)) {
					M[i][j] = M[i - 1][j - 1];
				} else {
					M[i][j] = getMin(M[i - 1][j], M[i - 1][j - 1], M[i][j - 1]) + 1;
				}
			}
		}
		// System.out.println(a + "와(과) " + b + "의 최소 편집 거리는 " + M[a.length() -
		// 1][b.length() - 1] + "입니다.");
		return M[a.length() - 1][b.length() - 1];
	}

	/*
	 * public void getTrace(int M[][], String a, String b) {
	 * System.out.println("[ " + b + "을(를) " + a + "로 바꾸는 과정 추적 ]"); int i =
	 * a.length() - 1; int j = b.length() - 1; while (!(i == 0 && j == 0)) { int
	 * s = getMin(M[i - 1][j], M[i - 1][j - 1], M[i][j - 1]); if (s == M[i][j])
	 * { i -= 1; j -= 1; } else { if (s == M[i][j - 1]) {
	 * System.out.println(b.charAt(j) + "을(를) 삭제합니다."); j -= 1; } else if (s ==
	 * M[i - 1][j - 1]) { System.out.println(b.charAt(j) + "을(를) " + a.charAt(i)
	 * + "(으)로 변경합니다."); i -= 1; j -= 1; } else { System.out.println(a.charAt(i)
	 * + "을(를) 추가합니다."); i -= 1; } } } }
	 */
	// 위 추적 부분을 매트릭스로 표현될 수 있도록 바꾸는 것.
	public static void main(String[] args) {
		String a = "abcdef";
		String b = "azced";
		Main m = new Main();
		// m.getDistance(a, b);
		// m.getTrace(m.M, a, b);
		//
		for (int i = 0; i < a.length(); i++) {
			System.out.print("\t" + a.charAt(i));
		}
		System.out.println();
		for (int i = 0; i < b.length(); i++) {
			System.out.print(b.charAt(i) + "\t");
			for (int j = 0; j < a.length(); j++) {
				System.out.print(m.getDistance(b.substring(0, i + 1), a.substring(0, j + 1)) + "\t");
			}
			System.out.println();
		}

	}

}

결과 :

 ↓

 

http://monny.tistory.com/66 이곳에 더 자세한 설명도 있습니다! 참고하세요~ㅎㅎ