영어 소문자로 된 문자열 A와 B가 주어진다. 어떤 문자열에서 글자 몇 개를 지우고(하나도 지우지 않아도 된다) 남은 글자를 원래 차례대로 이은 것을 그 문자열의 부분 수열이라 한다. 남는 글자는 이어져 있지 않아도 된다. 예를 들어 "ace"는 "abcde"의 부분 수열이지만 "aec"는 아니다. A의 부분 수열이면서 B의 부분 수열이기도 한 문자열 가운데 가장 긴 것의 길이를 출력하라. 공통인 글자가 하나도 없으면 0을 출력한다.
abcbdab bdcaba
4
abc def
0
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
L[i][j] = A의 앞 i글자와 B의 앞 j글자의 답이라 두면, 두 글자가 같을 때 L[i-1][j-1] + 1, 다를 때 max(L[i-1][j], L[i][j-1])이에요(동적 계획법).
표는 1,001 × 1,001 = 약 100만 칸이라 C·C++·Java·C#·Python·JavaScript·TypeScript는 2차원으로 만들어도 되지만, 크레이콘 목록은 한 개에 10,000칸까지라서 바깥 목록 1,001개에 안쪽 목록 1,001칸씩으로 쪼개야 해요.
바로 윗줄만 쓰니 한 줄(B 길이 + 1칸)로 줄이는 게 깔끔해요.
이때 함정: 왼쪽 칸 row[j - 1]은 이미 이번 줄 값으로 바뀌어 있어서, 윗줄의 왼쪽 위 칸(대각선)은 덮어쓰기 전에 diag 변수에 따로 챙겨야 해요 — 챙기지 않으면 "aa"와 "aaaa"의 답이 4가 돼요.
또 부분 수열은 건너뛰어도 되니 이어진 공통 부분 문자열("abxcd"·"abycd"에서 2)과 달라요(답 4).
앞에서부터 같은 글자를 바로 짝짓는 욕심도 틀려요("zabcd"·"abcdz"에서 z를 먼저 잡으면 1, 답 4).
한 글자씩 비교: Python·JavaScript·TypeScript는 b[j - 1]이 길이 1인 문자열, Java는 b.charAt(j - 1)(문자열에 []를 못 써요), C#·C·C++은 b[j - 1]이 char, 크레이콘도 b[j - 1]이 한 글자 문자열이고 각각 (ch 에서 a)로 글자를 돌아요.
입력 끝의 \r이나 빈칸이 글자로 섞이지 않게 줄을 읽으면 strip()·trim()·공백제거()를 해요(C·C++의 scanf("%s")·cin >>는 저절로 걸러요).
a = input().strip()b = input().strip()m = len(b) # row[j] = (a의 지금까지 읽은 앞부분)과 b[:j]의 가장 긴 공통 부분 수열 길이. 2차원 표 대신 한 줄만 둔다row = [0] * (m + 1)for ch in a: diag = 0 # 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for j in range(1, m + 1): up = row[j] if ch == b[j - 1]: row[j] = diag + 1 elif row[j - 1] > row[j]: row[j] = row[j - 1] diag = upprint(row[m])const [a, b] = require("fs").readFileSync(0, "utf8").split("\n").map((s) => s.trim());const m = b.length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다const row = new Array(m + 1).fill(0);for (const ch of a) { let diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (let j = 1; j <= m; j++) { const up = row[j]; row[j] = ch === b[j - 1] ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; }}console.log(row[m]);import { readFileSync } from "node:fs"; const [a, b]: string[] = readFileSync(0, "utf8").split("\n").map((s) => s.trim());const m: number = b.length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다const row: number[] = new Array<number>(m + 1).fill(0);for (const ch of a) { let diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (let j = 1; j <= m; j++) { const up = row[j]; row[j] = ch === b[j - 1] ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; }}console.log(row[m]);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String a = in.readLine().trim(); String b = in.readLine().trim(); int m = b.length(); // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 int[] row = new int[m + 1]; for (int i = 0; i < a.length(); i++) { char ch = a.charAt(i); int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b.charAt(j - 1) ? diag + 1 : Math.max(row[j], row[j - 1]); diag = up; } } System.out.println(row[m]); }}using System; class Program{ static void Main() { string a = Console.ReadLine().Trim(); string b = Console.ReadLine().Trim(); int m = b.Length; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 int[] row = new int[m + 1]; foreach (char ch in a) { int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b[j - 1] ? diag + 1 : Math.Max(row[j], row[j - 1]); diag = up; } } Console.WriteLine(row[m]); }}#include <algorithm>#include <iostream>#include <string>#include <vector> int main() { std::string a, b; std::cin >> a >> b; int m = static_cast<int>(b.size()); // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 std::vector<int> row(m + 1, 0); for (char ch : a) { int diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 for (int j = 1; j <= m; j++) { int up = row[j]; row[j] = ch == b[j - 1] ? diag + 1 : std::max(row[j], row[j - 1]); diag = up; } } std::cout << row[m] << "\n";}#include <stdio.h>#include <string.h> int main(void) { static char a[1002], b[1002]; scanf("%1001s %1001s", a, b); int n = (int)strlen(a), m = (int)strlen(b); /* row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이. 한 줄만 둔다 */ static int row[1001]; for (int i = 0; i < n; i++) { int diag = 0; /* 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 */ for (int j = 1; j <= m; j++) { int up = row[j]; if (a[i] == b[j - 1]) row[j] = diag + 1; else if (row[j - 1] > row[j]) row[j] = row[j - 1]; diag = up; } } printf("%d\n", row[m]); return 0;}a = 콘솔.줄읽기().공백제거();b = 콘솔.줄읽기().공백제거();m = b.길이; // row[j] = (a의 지금까지 읽은 앞부분)과 b의 앞 j글자의 가장 긴 공통 부분 수열 길이// 1,001 × 1,001 표 대신 한 줄(m + 1칸)만 둔다row = 새목록(m + 1, 0);각각 (ch 에서 a){ diag = 0; // 윗줄의 row[j - 1] — 덮어쓰기 전에 따로 챙긴다 반복 (j = 1; j <= m; j++) { up = row[j]; 만약 (ch == b[j - 1]) { row[j] = diag + 1; } 아니면 { row[j] = 수학.큰수(row[j], row[j - 1]); } diag = up; }}콘솔.쓰기(row[m]);