Common Child

사이트: HackerRank
난이도: 미디움
분류: String

문제

두 개의 문자열이 주어졌을 때 두 문자열의 최장공통수열(Longest Common Subsequence)을 반환하라.

최장공통수열은 두 문자열에서 공통 문자가 비연속적인 형태로 존재하는 수열중 가장 큰 수열을 의미한다. 주로 유전자 염기서열을 비교하는데 쓰인다고 하는데, 의외로 다음 문제처럼 유전자 비교 문제가 나오진 않았다.

SHINCHAN
NOHARAAA

위 두 개의 문자열 중 공통 문자를 가진 가장 큰 수열은 아래와 같다.

___N_HA_
N_HA____

1. 나의 풀이

문자열 문제는 풀 때 긴가민가한 문제들이 많은 것 같다. 해당 문제를 풀이하기 위해 이번에도 시간을 많이 쏟았는데 결국 다 해결하지 못했다. 해당 문자열 문제부터 적당히 시간을 끊고, 해결하지 못한 경우 해결방법을 찾고 최대한 문제유형에 익숙해 지는 것이 좋다고 생각하여 그렇게 진행하였다.

function commonChild(s1, s2) {
    // Write your code here
    const map = {};

    // s1의 모든 문자와 인덱스를 저장하고,
    Array.from(s1).forEach((c, i) => {
        if (!map[c]) {
          map[c] = [];
        }
        map[c].push(i);
    });

    const a1 = [], a2 = [];
    Array.from(s2).forEach((c, i) => {
        // s2와 일치하는 문자를 발견할 경우 각 문자열의 인덱스를 기록했다.
        if (map[c]) {
          a1.push(map[c].shift());
          a2.puhs(i);
        }
    });

    let count = 0;
  	// 기록된 인덱스를 연산하는 로직을 짜다가 시간을 너무 많이 잡아먹어 결국 완성하지 못했다.
    for (let i = 0; i < a1.length; i++) {
        for (let j = 0; j < a2.length; j++) {
          	const a1idx = a1[i];
        }
    }

    return count;
}

2. 다른사람의 풀이

해당 문제를 찾아보니까 DP(Dynamic Programming)를 사용하여 LCS(Longest Common Subsequence)를 구하는 문제라고 한다. 역시나 이런 개념들을 잘 숙지하고 있지 않으면 해결하기 어려운 문제이다.

LCS(Longest Common Subsequence) 알고리즘을 참고하길 바란다.

function commonChild(s1, s2) {
    // Write your code here
    const dp = [];
    dp[0] = new Array(s2.length + 1).fill(0);

    for (let i = 1; i <= s1.length; i++) {
        dp[i] = [];
        dp[i][0] = 0;

        for (let j = 1; j <= s2.length; j++) {
            if (s1.charAt(i - 1) === s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[s1.length][s2.length];
}