[HackerRank] Common Child

2019-06-21 글쓴이 TED HONG

[HackerRank] Common Child

주어진 두 문자열중 중복되는 문자를 찾고
연속으로 가장 길게 배치되는 글자 수를 찾는 문제.
(문제 이해하기가 어렵다;;;)

List에 넣어서 하나 하나 비교하는 방식으로 하다가
자꾸 오답이 나서 보니 문제를 잘못이해함.. ㅠ
멘붕와서 포기하고 풀이 검색을 해봤는데

정말 상상도 못할 방법으로 푼 해답을 발견했다.

아니… 대체 왜 이렇게 되는거냐고;;;

이런거 짜는 사람들은 대체 누굴까..;; 

 

https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

 static int commonChild(string s1, string s2)
        {
            char[] X = s1.ToCharArray();
            char[] Y = s2.ToCharArray();
            int m = X.Length;
            int n = Y.Length;

            int[,] L = new int[m + 1, n + 1];

            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i == 0 || j == 0)
                        L[i, j] = 0;
                    else if (X[i - 1] == Y[j - 1])
                        L[i, j] = L[i - 1, j - 1] + 1;
                    else
                        L[i, j] = Math.Max(L[i - 1, j], L[i, j - 1]);
                }
            }
            return L[m, n];
        }