코드
그리고 diff_match_patch 코드 필요함 (https://github.com/google/diff-match-patch)
public static void Main
(string
[] args
)
{
var tuples
= new List
<Tuple
<string, string,
int>>();
tuples.
Add(Tuple.
Create("kitten",
"sitting",
3));
tuples.
Add(Tuple.
Create("abc",
"ab",
1));
tuples.
Add(Tuple.
Create("ca",
"abc",
3));
tuples.
Add(Tuple.
Create("abc",
"cba",
2));
tuples.
Add(Tuple.
Create("abcd",
"bcde",
2));
tuples.
Add(Tuple.
Create("abababababa",
"aaaaaaaaaaa",
5));
tuples.
Add(Tuple.
Create("for",
"whileforif",
7));
tuples.
Add(Tuple.
Create("whilewhile",
"whalewhale",
2));
tuples.
Add(Tuple.
Create("aaabaaa",
"acacaca",
3));
tuples.
Add(Tuple.
Create("qwerty",
"dvorak",
5));
tuples.
Add(Tuple.
Create("asdf",
"asdf",
0));
foreach
(var tuple in tuples
)
{
var dmp
= new diff_match_patch
();
var text1
= string.
Join("\n\n", tuple.
Item1.
ToArray());
var text2
= string.
Join("\n\n", tuple.
Item2.
ToArray());
var diffs
= dmp.
diff_main(text1, text2
);
dmp.
diff_cleanupSemantic(diffs
);
var distance
= 0;
var independents
= new List
<Diff
>();
Diff temp
= null
;
for (var i
= 0; i
< diffs.
Count; i
++)
{
var current
= diffs
[i
];
if (current.
operation == Operation.
EQUAL)
{
if (temp
!= null
)
{
independents.
Add(temp
);
temp
= null
;
}
continue;
}
if (temp
!= null
)
{
var change1
= temp.
text.
Replace("\n",
"");
var change2
= current.
text.
Replace("\n",
"");
distance
+= Math.
Max(change1.
Length, change2.
Length);
temp
= null
;
}
else
{
temp
= current
;
}
}
if (temp
!= null
)
{
independents.
Add(temp
);
}
foreach
(var diff in independents
)
{
distance
+= diff.
text.
Replace("\n",
"").
Length;
}
var result
= tuple.
Item3 == distance
;
Console.
WriteLine($
"'{tuple.Item1}' vs '{tuple.Item2}' is require be {tuple.Item3}\n\tcalculated = {distance} => {result}");
if (result
== false)
{
Console.
WriteLine("What's wrong?");
}
Console.
WriteLine();
}
}
출력
주딱이 제시한 입력과 백준 문제의 모든 예제 입력에 대하여
계산된 결과가 각 예제 출력과 동일함
'kitten' vs 'sitting' is require be 3
calculated = 3 => True
'abc' vs 'ab' is require be 1
calculated = 1 => True
'ca' vs 'abc' is require be 3
calculated = 3 => True
'abc' vs 'cba' is require be 2
calculated = 2 => True
'abcd' vs 'bcde' is require be 2
calculated = 2 => True
'abababababa' vs 'aaaaaaaaaaa' is require be 5
calculated = 5 => True
'for' vs 'whileforif' is require be 7
calculated = 7 => True
'whilewhile' vs 'whalewhale' is require be 2
calculated = 2 => True
'aaabaaa' vs 'acacaca' is require be 3
calculated = 3 => True
'qwerty' vs 'dvorak' is require be 5
calculated = 5 => True
'asdf' vs 'asdf' is require be 0
calculated = 0 => True
코드 형상비교할 때 사용하던 방법을 좀 활용했음
순서로 표현하면 아래와 같음
여기서 말하는 '결과 값'은 변경하는 연산 횟수임
1. 입력 문자열 2개에 각각 줄바꿈 문자를 '2개' 넣어서 각 문자를 완벽하게 분리함 (diff-match-patch가 문자 단위로 쪼개주는걸 못함
2. 두 문자열을 비교 결과 목록 취득 (추가, 삭제, 일치)
3. 각 비교 결과에서 인접한 추가, 삭제끼리 묶는다
4. 묶인 두 비교 결과의 각 문자열의 길이 중 높은 값 만큼 '결과 값' 증가 (줄바꿈 문자 제외)
5. 인접한 삽입/삭제가 없는 경우 해당 결과의 문자열 길이 만큼 '결과 값' 증가 (줄바꿈 문자 제외)
6. 끝
json때는 문서보고 각잡고 만들었는데,
이번거는 백준 문제로도 있으니까 나보다 잘짜는 많은 사람이
직접 알고리즘 만들어서 풀어봤을테니까 다른 방법으로 풀어보기로 함
댓글 0