문제

---

두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.

A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.

• 삽입: A의 한 위치에 문자 하나를 삽입한다.
• 삭제: A의 문자 하나를 삭제한다.
• 교체: A의 문자 하나를 다른 문자로 교체한다.
  두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

---

첫째 줄에 최소 편집 횟수를 출력한다.

풀이 코드 (Java)

import java.io.InputStreamReader;
import java.io.BufferedReader;

public class Main {

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		String t = br.readLine();
		
		int dp[][] = new int[s.length() + 1][t.length() + 1];
		for(int i = 0; i < s.length(); i++) {
			dp[i + 1][0] = i + 1;
		}
		for(int j = 0; j < t.length(); j++) {
			dp[0][j + 1] = j + 1;
		}
		
		for(int i = 0; i < s.length(); i++) {
			for(int j = 0; j < t.length(); j++) {
				if(s.charAt(i) == t.charAt(j)) {
					dp[i + 1][j + 1] = dp[i][j];
				}
				else {
					dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1] + 1, dp[i + 1][j] + 1), dp[i][j] + 1);
				}
			}
		}
		
		System.out.println(dp[s.length()][t.length()]);

	}

}

알고리즘 시험 공부 중 나온 편집 거리 문제..

문자열 S, T가 주어졌을때
S의 부분 문자열 s0~si를 T의 부분 문자열 t0~tj로 변환해야 하는 상황이다.
하나의 문자에 대하여 3가지 연산(삽입, 삭제, 수정)이 가능하다면 변환할때 드는 연산의 최소 횟수(편집 거리)는?

dp[i][j] : s0~si -> t0~tj 의 편집 거리
를 나타내는 dp[][]를 설정해주고
점화식을 s[i] = t[j]일때와 아닐때로 나누어 잘 정해주면 풀 수 있는 문제였다.

오랜만에 Eclipse사용해서 Java로 문제를 풀어봤는데 역시 백준은 자바다.
나중에 입력값 잘 정제해서 Js로도 문제 많이 풀어야지..!!