[백준 20542번] 받아쓰기 (python)

문제

세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 받아쓰기 채점 프로그램을 통해 지원자가 작성한 답안에 점수를 매긴다. 지원자가 작성한 답안을 몇 번이나 수정해야 정답과 같아지는지 확인하는 방법이다. 수정에는 추가, 삭제, 변환 세 가지 방법이 있다. 추가는 한 글자를 추가하는 것이고, 삭제는 한 글자를 삭제하는 것이며, 변환은 한 글자를 다른 글자로 바꾸는 것을 의미한다. 추가, 삭제, 변환은 모두 동일하게 1회의 수정으로 취급한다. 다음은 각 수정 방법의 예를 나타낸 표이다.

	답안	정답	수정 사항	수정
추가	piza	pizzaa	z,a 추가	2회
삭제	pineapple	apple	p,i,n,e 삭제	4회
변환	johnber	johnson	b->s, e->o, r->n 으로 각각 변환	3회
종합	fishcake	taken	f->t  변환 / i,s,h,c 삭제 / n 추가	6회

받아쓰기 테스트에서의 수정 횟수는 추가, 삭제, 변환 세 가지 수정 횟수의 합이 가장 최소로 일어난 경우를 말한다. 그리고 받아쓰기 테스트 점수는 작성한 답안을 정답으로 바꿀 때 필요한 총 수정 횟수와 같다. 만약 총 세 번의 수정이 일어났다면 3점을 획득하는 것이다. 0점이 제일 좋은 점수이다.

승연이는 CTP에 입사하기 위해 영어 받아쓰기를 공부중이다. 그러던 중 기가막힌 방법을 알게 되었는데, 그것은 바로 i와 v를 휘갈겨 쓰는 것이다. 실제로 CTP의 채점 시스템은 종이에 작성한 답안을 카메라로 인식해 정답과 비교하기 때문에, 휘갈겨 쓴 글자를 잘못 인식하는 에러가 있다. 휘갈겨 쓴 i는 i, j, l 모두와 매칭된다. 예를 들어 정답이 'james'일 때 답안이 'iames'라면 수정 횟수는 0회로 채점된다.대신 답안에 작성한 j와 l은 정확하게 인식한다. 마찬가지로 휘갈겨 쓴 v는 v, w와 매칭된다. 정답이 'warren'일 때 답안이 'varren'이라면 채점 결과는 0점이다. 단, w는 정확히 인식하기 때문에, 정답이 'vaccine'일 때 답안이 'waccine'이라면 점수는 1점으로 채점된다. 다시 한 번 정리하자면 i와 v를 제외한 모든 글자는 정확히 인식한다. 미리 자신의 점수를 확인해보고싶어하는 승연이를 위해 받아쓰기 점수를 계산하는 프로그램을 만들어보자!

 

기록

(dp 16일차) LCS로 풀려고 이리저리 시도해봤는데 안되서 구글링했다. 편집거리 알고리즘 알게되서 바로 적용해봤더니 성공했다:)

 

이번 문제는 편집거리 알고리즘에 비교조건(v=w, i=j,l)을 추가해서 푸는 문제였다. 편집거리 알고리즘은 두 문자열의 유사도를 판단하는 기준으로, 문자열을 같게 하는 최소의 편집횟수(추가, 변환, 삭제)를 구하는 알고리즘이다. 문제의 예시로 설명하겠다.

 

1. 먼저 아래와 같이 초기화 해준다.

빈 문자열에서 'taken'를 만들기 위해서는 각 인덱스만큼의 편집(추가)이 필요하고, 마찬가지로 'fishcake'를 빈문자열로 만들기 위해서는 각 인덱스만큼의 편집(삭제)이 필요하다.

		t	a	k	e	n
	0	1	2	3	4	5
f	1
i	2
s	3
h	4
c	5
a	6
k	7
e	8

 

2. 비교문자가 다른 경우의 편집거리를 구하는 방법이다.

아래의 경우, 'fi'로 'ta'를 만들기 위한 편집거리를 구해보자. 이전 결과에서 3가지 편집(추가, 삭제, 수정)이 가능하다. 'fi'와 't'에서 결과단어에 'a'가 추가됐으므로 'a' 추가, 'f'와 'ta'에서 입력단어에 'i'가 추가됐으므로 'i' 삭제, 'f'와 't'에서 입력단어 'i'와 결과단어 'a'가 추가됐으므로 'i'->'a' 변환을 선택할 수 있다. 이 때, 최소 편집거리를 구해야 하기 때문에 변환하는 경우(대각선 방향)를 선택하여 1을 더해 저장한다.

		t	a	k	e	n
	0	1	2	3	4	5
f	1	1(변환)	2(삭제)	3	4	5
i	2	2(추가)	2
s	3
h	4
c	5
a	6
k	7
e	8

 

3. 비교문자가 같은 경우의 편집거리를 구하는 방법이다.

이번엔 'fishca'로 'ta'를 만들기 위한 편집거리를 구할 것이다. 현재 비교하는 문자는 'a'로 같다. 이 경우, 같은 문자인 'a' 가 추가됐기 때문에 'fishc'와 't'에서의 편집횟수와 같다. 따라서 대각선 방향의 숫자를 그대로 가져와 저장한다.

		t	a	k	e	n
	0	1	2	3	4	5
f	1	1	2	3	4	5
i	2	2	2	3	4	5
s	3	3	3	3	4	5
h	4	4	4	4	4	5
c	5	5	5	5	5	5
a	6	6	5
k	7
e	8

 

다 채워진 편집거리 배열은 다음과 같다. 따라서 'fishcake'와 'taken'의 편집거리는 6이 된다.

		t	a	k	e	n
	0	1	2	3	4	5
f	1	1	2	3	4	5
i	2	2	2	3	4	5
s	3	3	3	3	4	5
h	4	4	4	4	4	5
c	5	5	5	5	5	5
a	6	6	5	6	6	6
k	7	7	6	5	6	7
e	8	8	7	6	5	6

 

코드

n, m = map(int, input().split())
w1 = input()
w2 = input()

dp = [[i]+[0]*m for i in range(n+1)]
dp[0] = [i for i in range(m+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
        if w1[i-1]==w2[j-1] or (w1[i-1]=='v' and w2[j-1]=='w') or (w1[i-1]=='i' and w2[j-1] in ['j', 'l']):
            dp[i][j] = dp[i-1][j-1]
print(dp[n][m])

1. 입력문자와 결과문자의 편집거리를 저장할 이차원 배열 dp를 생성하여 초기화한다.

2. 입력문자가 같다면 (v=w, i=j,l 비교조건 포함) dp[i-1][j-1]을 그대로 저장하고, 다르다면 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])에 1을 더해 저장한다.

3. 두 문자의 편집거리를 출력한다.