문자열 압축하기
연속되는 문자열에 대해서 같은 문자가 2개 이상 연속하는 경우 aaa -> a3와 같이 변경하여 문자열을 압축한다.
출처 : https://www.hackerrank.com/challenges/string-compression/problem
이를 위해서는 aabbccdd -> aa,bb,cc,dd로 분해하는 함수가 필요한데, group 함수가 여기에 딱이다. (Data.List에 포함되어 있다.)
encode :: String -> [String]
encode = concapMap (\x -> [(head x):"", p x]) . group
where p a = if (> 1) . length a
then show . length x
else ""
혹은 다음과 같이 1을 뺄 수 있다.
encode = concat . filter (/= "1") .
concatMap (\x -> [head x:"", show . length $ x]) .
group
접두어 압축
두 문자열이 동일한 부분열로 시작하는 경우, 최대 공통 부분열을 구하고 나머지 문자열에서는 공통열을 제외한 나머지들을 각각 추려낸다.
두 개의 문자열을 입력받아 이 처리를 한 후 공통열과 잔여분의 각각의 길이와 해당 문자열을 출력하는 프로그램을 작성하라. 이 때 각 문자열은 모두 소문자 알파벳으로만 구성되어 있다.
접근
String은 [Char] 타입이므로 간단하게 다음과 같이 정의되는 함수를 하나 생각할 수 있다.
- 이 함수는 공통열, 문자열1, 문자열2를 인자로 받는다.
- 최종적으로 [공통열, 문자열1, 문자열2]로 쪼개진 리스트를 리턴하게끔한다.
- 문자열1, 2에서 첫글자가 공통인 경우 이 글자를 공통열의 뒤에 더하고, 나머지 분량에 대해 재귀호출한다.
- 문자열 1, 2 중 하나가 빈 문자열이면 현재 인자들을 리스트로 연결하여 리턴한다.
- 문자열 1, 2의 첫글자가 서로 다르면 인자들을 리스트로 연결하여 리턴한다.
compareString :: String -> String -> String -> [String]
compareString px a b
| null a || null b = [px, a, b]
| (head a) /= (head b) = [px, a, b]
| otherwise = compareString (px ++ [head a]) (tail a) (tail b)
main = do
s1 <- getLine
s2 <- getLine
let result = compareString "" s1 s2
putStrLn $ unlines . map (\x ->
(show . length $ x) ++ " " ++ x) $ result
이 코드는 성공적으로 수행된다. 그런데 실제로 이 코드를 제출하면 성능에 문제가 생긴다. 특정 길이 이상으로 비교해야할 문자열이 커지고, 공통열의 길이가 길어지면 길어질수록 성능이 떨어진다.
여기서 성능에 영향을 주는 부분은 바로 px ++ [x]이다. 하스켈의 리스트는 재귀적인 구조이다. 따라서 px++ [x]는 매 시행마다 마지막 원소까지 거슬러 간 후에 이를 [x]에 덧붙이고, 남은 px에 대해서 계속 이를 반복한다.
px ++ [x]가 느린대신에 앞으로 붙이는 것은 별 부담이 없다. 따라서 x:px로 대체한 다음 최종 결과에서 reverse px로 이를 뒤집는 것이 좀 더 나은 성능을 보인다.
compareString :: String -> String -> String -> [String]
compareString px a b
| null a || null b = [reverse px, a, b]
| (head a) /= (head b) = [reverse px, a, b]
| otherwise = compareString ((head a):px) (tail a) (tail b)
다른 접근법
좀 더 멋진 접근법을 생각해보자. 두 문자열을 앞에서부터 비교해나간다. 두 글자가 같으면 그 글자로, 다른 글자이면 '.'으로 교체한다. 이렇게 합쳐지는 글자에 대해서 앞에서부터 .이 아닌 영역을 추슬러 그 길이를 구하면 공통열의 길이가 나온다.
이 방식은 위의 재귀적인 해법보다 빠를 수 있는데, 두 문자열의 전체를 비교하는 것이 아니라 느긋하게 평가하기 때문에 실제로 서로 다른 문자열이 나오는 지점까지만 체크하기 때문이다.
이를 이용해서 문제를 풀어보자.
test :: String -> String -> Int
test a b = length . takeWhile (/= '.') .
zipWith (\x y -> if x == y then x else '.' ) a $ b
main = do
a <- getLine
b <- getLine
let n = test a b
putStrLn $ (show n) ++ " " ++ (take n a)
putStrLn $ (show $ length a - n) ++ " " ++ (drop n a)
putStrLn $ (show $ length b - n) ++ " " ++ (drop n b)