20542번: 받아쓰기
세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는
www.acmicpc.net
문제
세계적인 기업 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를 제외한 모든 글자는 정확히 인식한다. 미리 자신의 점수를 확인해보고싶어하는 승연이를 위해 받아쓰기 점수를 계산하는 프로그램을 만들어보자!
입력
첫 번째 줄에 승연이가 작성한 답안의 길이 n, 정답의 길이 m이 공백을 두고 차례로 주어진다.
두 번째 줄에 승연이가 작성한 답안이, 세 번째 줄에 정답이 주어진다.
승연이가 작성한 답안과 정답은 모두 영어 소문자로만 이루어진다.
출력
첫 번째 줄에 승연이의 점수를 출력한다.
제한
- 1 ≤ n ≤ 1,000,000
- 1 ≤ m ≤ 1,000,000
- 1 ≤ n × m ≤ 10,000,000
코드
n, m = map(int, input().split())
sy = input()
answer = input()
matrix = [[0] * (n+1) for _ in range(m+1)]
for i in range(m+1):
matrix[i][0] = i
for j in range(n+1):
matrix[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if answer[i-1] == sy[j-1]:
matrix[i][j] = matrix[i-1][j-1]
elif sy[j-1] == 'i' and (answer[i-1] == 'j' or answer[i-1] == 'l'): # 휘갈겨 쓴 i
matrix[i][j] = matrix[i-1][j-1]
elif sy[j-1] == 'v' and (answer[i-1] == 'w'): # 휘갈겨 쓴 v
matrix[i][j] = matrix[i-1][j-1]
else:
matrix[i][j] = min(matrix[i-1][j], matrix[i]
[j-1], matrix[i-1][j-1]) + 1
print(matrix[m][n])
이 유형의 문제는 편집거리 알고리즘으로 풀 수 있는 문제이다.
편집거리 알고리즘은 다이나믹 프로그래밍의 일종으로 두 문자열 간의 유사도를 계산하는 알고리즘이다. 문자열 A에서 B로 추가, 삭제, 변환 3가지의 수정 방법을 이용한다고 할 때 편집 거리를 저장하는 배열을 생성하면 다음과 같다.
배열의 값으로는 변환하는데 필요한 최소 수정 횟수가 저장된다.
두 문자열을 한 문자씩 비교하며 편집거리를 구하는 것인데 비교하는 두 문자가 같다면 편집이 필요가 없기 때문에 각 문자열의 한 문자 이전의 편집거리 값을 갖고 오면 된다. 말로 하면 설명이 어려우니 그림을 보면 편하다.
fishca와 ta를 비교할 때 둘 다 현재 비교하는 문자는 a로 같으므로 fishc와 t의 편집거리를 그대로 갖고 온다.
만약 비교하는 문자가 다르다면 수정이 필요한 것이다. 이 경우에는 추가, 삭제, 변환 3가지로 나눌 수 있다.
예를 들어, fis와 ta를 비교한다고 해보자. 현재 비교하는 문자는 두 문자열의 가장 오른쪽 문자인 s와 a로, 다르다는 것을 알 수 있다. 그렇다면 fis와 ta의 최소 편집거리를 구하기 위해서는 3개의 값을 비교해보면 된다.
- 추가 : ta의 뒤에 s를 추가
- 삭제 : fis에서 s 삭제
- 변환 : ta => ts로 변환
우리는 수정 횟수가 최소인 경우를 구하는 것이기 때문에 3개의 값 중 가장 작은 값을 저장하면 된다.
이렇게 하여 배열의 가장 오른쪽 아래 값을 구하면 두 문자열의 최소 수정 횟수를 구할 수 있다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 3067번 Coins (0) | 2023.10.13 |
---|---|
[Python/파이썬] 백준 2629번 양팔저울 (0) | 2023.10.10 |
[Python/파이썬] 백준 4811번 알약 (0) | 2023.09.13 |
[Python/파이썬] 백준 13707번 합분해 2 (0) | 2023.09.08 |
[Python/파이썬] 백준 14226번 이모티콘 (0) | 2023.09.06 |