Chap 16. DP - Q36. 편집 거리

  • 0
  • 0
0
0

1. 편집 거리

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

A. 📜 문제

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

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

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

a. 예를 들면.

sundaysaturday의 최소 편집 거리는 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년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.