최소 편집 거리 알고리즘을 사용했습니다.
2차원의 표를 그리고 'A'문자열이 'B'문자열이 되기 위해 몇번의 편집이 필요한지 DP를 통해 계산합니다.
삽입. 삭제, 교체를 구분하지 않고 한 번의 편집으로 생각합니다.
문제명 : 카우버거 알바생
시간 복잡도 : , 공간 복잡도 :
1. 풀이 과정
시간 관계상 perplexity의 도움을 받았습니다.
knapsack의 변형이라고 합니다.
2차원 배열 dp[버거 + 1][감튀 + 1] 를 만듭니다.
예) 2개의 버거 1개의 감튀 주문이라면 dp[2] 부터 마지막까지 dp[2][1] 부터 마지막 까지 주문 수 1을 증가 시킵니다.
nextDP는 메모리절약을 위해 3차원으로 해결하는 분제를 2차원으로 해결하게 합니다.
문제명 :
최소 편집1. 풀이 과정
문제명 :
카우버거 알바생1. 풀이 과정