LCS 2 성공스페셜 저지
시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 | 256 MB | 18407 | 7518 | 5622 | 41.253% |
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.
예제 입력 1 복사
ACAYKP CAPCAK
예제 출력 1 복사
4 ACAK
알고리즘 분류
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.lang.Integer.max
import java.lang.StringBuilder
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main()=with(br){
val str1 = readLine()
val str2 = readLine()
val lcs = Array(str1.length+1,{IntArray(str2.length+1,{0})})
for(i in 1 until str1.length+1){
for(j in 1 until str2.length+1){
if(str1[i-1]==str2[j-1]){
lcs[i][j] = lcs[i-1][j-1]+1
}
else{
lcs[i][j] = max(lcs[i][j-1],lcs[i-1][j])
}
}
}
bw.write("${lcs[str1.length][str2.length]}\n")
if(lcs[str1.length][str2.length]>0) {
var i = str1.length
var j = str2.length
var ans = ""
while (i > 0) {
if (lcs[i][j] == lcs[i - 1][j]) {
i--
} else if (lcs[i][j] == lcs[i][j - 1]) {
j--
} else {
i--
j--
ans = str1[i] + ans
}
}
bw.write("$ans")
}
bw.flush()
bw.close()
}
|
cs |
'알고리즘 공부 > 문자열' 카테고리의 다른 글
백준 9251번 with Kotlin (0) | 2021.09.02 |
---|