Chap 16. DP - Q36. 편집 거리

1. 편집 거리

• 난이도
  • 중하
• 풀이 시간
  • 30분
• 시간 제한
  • 2초
• 메모리 제한
  • 128MB
• 출처
  • Goldman Sachs 인터뷰

A. 📜 문제

두 개의 문자열 A, B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다.

1. 삽입 (Insert)
   • 특정한 위치에 하나의 문자를 삽입한다.
2. 삭제 (Remove)
   • 특정한 위치에 있는 하나의 문자를 삭제한다.
3. 교체 (Replace)
   • 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다.

편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하라.

a. 예를 들면.

sunday와 saturday의 최소 편집 거리는 3이다.

b. 입력 조건

• 두 문자열 A, B가 한 줄에 하나씩 주어진다.
• 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같다.

c. 출력 조건

• 최소 편집 거리를 출력한다.

d. 테스트 케이스

• 입력 예시

  
  cat
  cut
  
  

  
  sunday
  saturday
  
  

• 출력 예시

  
  1
  
  

  
  3
  
  

B. 💡 내 답안

a. 😊 1차 시도 (성공)

A = input()
B = input()
answer = 0

point = 0

if len(A) < len(B):
    # 삽입
    answer += len(B) - len(A)
# elif len(A) > len(B):
#     # 삭제
#     answer += len(A) - len(B)

for i in range(len(A)):
    # `ssy`에서 `s`같이 중복되는 문자열을 방지하기 위해서, [point:]을 함
    if A[i] in B[point:]:
        point = B.index(A[i]) + 1
    else:
        # 교체
        answer += 1

print(answer)

a. 🙄 회고

내 풀이

• 코너 케이스까지 고려해가며 코드를 작성했다.
  • 입력 예시로 제시되지 않은 abcde, de도 생각하며 풀었다.
• DP문제인데 DP로 풀지 못했다.

결론

• 문자열 비교 문제를 DP로 풀기 위해 행렬처럼 만들고 푼, 답지의 풀이가 참 인상적이었다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

아래는 책 답지 풀이.

a. 책 답안

python-for-coding-test/6.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년