Leetcode 75 day23 (Longest Common Subsequence, Koko Eating Bananas, Edit Distance)

DP 2문제, 이진 검색 1문제를 풀었다. 꽤 오래전에 풀어본 문제긴 하지만 실마리가 전혀 보이지 않는 문제들이었다 😭.. 

1143. Longest Common Subsequence

문자열 text1, text2가 주어졌을 때 가장 긴 공통 subsequence를 구하라. subsequence는 원래 문자열에서 생성된 새 문자열로, 나머지 문자의 상대적 순서를 변경하지 않고 일부 문자(없을 수도 있음)를 삭제한 문자열이다. 

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

솔루션을 보기는 했는데, 부분 문제를 잘 정의하면 풀 수 있었을 것 같다.

text1의 길이를 len1, text2의 길이를 len2라고 정의했을 때, (len1+1) * (len2+1)인 2차원 배열 seq를 만든다. seq[i][j]은 text1의 길이가 i, text2의 길이가 j일 때 subsequence의 길이를 저장한다. seq[i+1][j+1]은 text1의 i번째 문자와 text2이 j번째 문자가 같다면, seq[i][j] + 1이고, 다르다면 max(seq[i+1][j], seq[i][j+1])이다.

이 문제와 관련된 알고리즘도 참고해 보길 바란다.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        int[][] seq = new int[len1+1][len2+1];
        for(int r=0; r<len1; r++) {
            for(int c=0; c<len2; c++) {
                seq[r+1][c+1] = (text1.charAt(r) == text2.charAt(c)) ? seq[r][c] + 1 : Math.max(seq[r+1][c], seq[r][c+1]);
            }
        }
        return seq[len1][len2];
    }
}

시간 복잡도는 O(len1 * len2), 공간 복잡도는 O(len1 * len2)이다.

875. Koko Eating Bananas

번역하기 힘들어서 ChatGPT의 도움을 받아서 문제 설명을 번역 & 요약해 봤다.

코코는 바나나를 먹는 것을 좋아합니다. n 개의 바나나 더미가 있으며, i 번째 더미에는 piles[i] 개의 바나나가 들어 있습니다. 경비원들은 떠났다가 h 시간 후에 돌아올 예정입니다. 코코는 1 시간당 먹는 속도인 k를 결정할 수 있습니다. 매 시간마다 바나나 더미 중 하나를 선택하고 그 더미에서 k 개의 바나나를 먹습니다. 만약 더미에 남은 바나나가 k 개보다 적다면, 남은 바나나를 모두 먹고 그 시간 동안은 더 이상 바나나를 먹지 않습니다. 코코는 천천히 먹는 것을 선호하지만 경비원들이 돌아오기 전에 모든 바나나를 다 먹고 싶어합니다. 목표는 모든 바나나를 h 시간 이내에 먹을 수 있는 최소한의 정수 k를 반환하는 것입니다.

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours.

이번에도 역시 솔루션을 참고.. 😭 k의 값은 1부터 max(piles)로 정의할 수도 있고, piles[i]에 올 수 있는 최댓값인 10^9로 정의할 수도 있다. piles를 h 시간 안에 먹을 수 있는 lower bound를 이진 탐색으로 찾으면 된다.

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1;
        int right = 1000000000;
        
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(canEatInTime(piles, mid, h)) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
    public boolean canEatInTime(int piles[], int k, int h){
        long hours = 0; // can overflow
        for(int pile : piles){
            int div = pile / k;
            hours += div;
            if(pile % k != 0) hours++;
        }
        return hours <= h;
    }
}

piles 배열의 길이를 n이라고 하면, canEatInTime은 배열의 모든 인자를 순회해야 하기 때문에 O(n)이고, 이진 검색은 O(log10^9)가 소요된다. 그러면 시간 복잡도는 O(log10^9 * n) = O(n)이 된다.

공간 복잡도는 O(1)이다.

72. Edit Distance

문자열 word1, word2가 주어졌을 때 word1을 word2로 변경하는데 필요한 최소한의 명령의 수를 반환하라.

  - 문자 추가

  - 문자 삭제

  - 문자 교체

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
  - Insert a character
  - Delete a character
  - Replace a character

동적 프로그래밍 문제는 1. 재귀적으로 문제를 풀고, 2. 캐시/memoization을 이용해서 최적화시키고, 3. bottom-up 방식으로 변경하면 어떤 문제든 풀 수 있다고 한다. 그런데 첫 번째 단계가 어려운 경우도 있고, 중복되는 부분 문제를 찾지 못해서 2단계로 못 가는 경우도 있는 것 같다. DP는 막히면 아예 안 풀릴 때가 많아서 힘이 빠지지만, 일단 문제를 풀면서 답을 정의하는 연습을 많이 해야 할 것 같다. 내가 참고한 솔루션. 1단계, 2단계, 3단계 차례로 솔루션과 직관을 함께 알려줘서 읽어볼 만하다.

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();

        char[] c1 = word1.toCharArray();
        char[] c2 = word2.toCharArray();

        int[][] matched = new int[c1.length+1][c2.length+1];

        for(int i=0; i<=c1.length; i++) {
            matched[i][0] = i;
        }
        for(int j=0; j<=c2.length; j++) {
            matched[0][j] = j;
        }

        for(int i=0; i<c1.length; i++) {
            for(int j=0; j<c2.length; j++) {
                if (c1[i] == c2[j]) {
                    matched[i+1][j+1] = matched[i][j];
                } else {
                    matched[i+1][j+1] = Math.min(matched[i][j+1], Math.min(matched[i+1][j], matched[i][j])) + 1;
                }
            }
        }
        
        return matched[c1.length][c2.length];
    }
}