문제

가장 긴 공통 부분 문자열(Longest Common Subsequence)이란 A, B 두 문자열이 주어졌을 때 두 열에 공통으로 들어 있는 요소로 만들 수 있는 가장 긴 부분열을 말합니다. 여기서 부분열이란 다른 문자열에서 몇몇의 문자가 빠져 있어도 순서가 바뀌지 않은 열을 말합니다.

예를 들어 S1 = ['T', 'H', 'I', 'S', 'I', 'S', 'S', 'T', 'R', 'I', 'N', 'G', 'S'] S2 = ['T', 'H', 'I', 'S', 'I', 'S']라는 두 문자열이 있을 때 둘 사이의 부분 공통 문자열의 길이는 ['T', 'H', 'I', 'S', 'I', 'S']의 6개가 됩니다.

이처럼 두 문자열이 주어지면 가장 긴 부분 공통 문자열의 길이를 반환하는 프로그램을 만들어 주세요.

두 개의 문자열이 한 줄에 하나씩 주어집니다. 문자열은 알파벳 대문자로만 구성되며 그 길이는 100글자가 넘어가지 않습니다.

출력은 이 두 문자열의 가장 긴 부분 공통 문자열의 길이를 반환하면 됩니다.

// 입력
THISISSTRINGS
THISIS

// 출력
6

// 입력
THISISSTRINGS
TATHISISKKQQAEW

// 출력
6

// 입력
THISISSTRINGS
KIOTHIKESSISKKQQAEW

// 출력
3

// 입력
THISISSTRINGS
TKHKIKSIS

// 출력
3

풀이

/**
 * 가장 긴 공통 부분 문자열을 반환하는 함수
 * @param {string} input 줄바꿈으로 구분된 문자열
 * @returns {string} 가장 긴 공통 부분 문자열
 */
function getLongestCommonSubsequence(input) {
  // input을 줄바꿈을 기준으로 둘로 나눠서 각각 할당합니다.
  const [firstString, secondString] = input.split("\n");
  // 각각의 문자열로 부분열의 배열을 만듭니다.
  const firstSubsequences = getSubsequences(firstString);
  const secondSubsequences = getSubsequences(secondString);

  // 두 부분열의 공통 부분 문자열의 배열을 만듭니다.
  const commonSubsequences = firstSubsequences.filter((subsequences) =>
    secondSubsequences.includes(subsequences)
  );

  // 공통 부분 문자열을 각 문자열의 길이를 기준으로 오름차순 정렬합니다.
  const sorted = commonSubsequences.sort((a, b) => a.length - b.length);
  // 길이가 제일 긴 공통 부분 문자열을 반환합니다.
  const longestCommonSubsequence = sorted.pop();

  return longestCommonSubsequence;
}

/**
 * 특정 문자열의 부분열들의 배열을 반환하는 함수
 * @param {string} sequence 문자열
 * @returns {Array<string>}부분열들의 배열
 */
function getSubsequences(sequence) {
  // 부분열을 저장할 배열을 만듭니다.
  const subsequences = [];
  // 인자로 들어온 문자열을 배열로 만듭니다.
  const strings = sequence.split("");

  // 이중 for문으로 부분열을 만들어 배열에 저장합니다..
  for (let i = 0; i <= sequence.length; i++) {
    for (let j = i + 1; j <= sequence.length; j++) {
      subsequences.push(strings.slice(i, j).join(""));
    }
  }

  // 부분열의 배열을 반환합니다.
  return subsequences;
}

const input = `THISISSTRINGS
TKHKIKSIS`;

// 가장 긴 공통 부분 문자열을 구해서 그 길이를 할당한다.
const longestCommonSubsequenceLength = getLongestCommonSubsequence(input).length;
console.log(longestCommonSubsequenceLength);

부분열의 배열 만드는 법

문자열 string의 부분열이 담긴 배열을 이중 for문과 slice()를 이용해서 만든다고 할 때,
slice(i, j)에 들어가는 숫자 i, j와 해당 문자열을 정리해보면 아래의 표와 같다.

slice( i, j )	문자열	slice( i, j )	문자열	slice( i, j )	문자열	slice( i, j )	문자열	slice( i, j )	문자열	slice( i, j )	문자열
0, 1	s	0, 2	st	0, 3	str	0, 4	stri	0, 5	strin	0, 6	string
1, 2	t	1, 3	tr	1, 4	tri	1, 5	trin	1, 6	tring
2, 3	r	2, 4	ri	2, 5	rin	2, 6	ring
3, 4	i	3, 5	in	3, 6	ing
4, 5	n	4, 6	ng
5, 6	g

i = 0일 때 j = 1 ~ 6,
i = 1일 때 j = 2 ~ 6,
i = 2일 때 j = 3 ~ 6,
i = 3일 때 j = 4 ~ 6,
i = 4일 때 j = 5 ~ 6,
i = 5일 때 j = 6이므로, 이를 이중 for문으로 만들면 아래의 코드가 된다.

// sequence는 인자로 들어온 문자열에 split을 사용해 만든 배열
for (let i = 0; i <= sequence.length; i++) {
  for (let j = i + 1; j <= sequence.length; j++) {
    subsequences.push(strings.slice(i, j).join(""));
  }
}