조금 어려운 초급 연습문제. 어떤 임의의 정수 N을 소인수 분해한 결과가 다음과 같다고 하자.
$$ p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times p_2^{a_4} ... $$
이를 [p1, a1, p2, a2, p3, a3 ... ]의 리스트로 표현하기로 약속한다. 리스트의 개수 N을 입력받고 이후 N 줄에 대해서 각각 공백으로 띄워진 숫자리스트를 입력받는다. 리스트는 인수와 지수의 짝이어야 하므로 짝수개의 인자가 들어오는 것을 보장한다.
자 이렇게 구성된 N 개의 정수들의 최대 공약수를 구해서 입력과 동일한 형태의 리스트로 출력하는 프로그램을 작성해보자.
접근
가장 손쉬운 방법은 Integer 타입으로 만들어서 gcd 함수를 적용하는 것이다. 이는 만들어지는 각 정수가 그럭저럭 큰 범위에서는 나쁘지 않게 작동할지도 모르겠다. 하지만 이미 소인수분해된 결과가 있는 만큼, 리스트를 이용하는 범위 내에서 처리하도록 한다.
우선 리스트의 홀/짝번째 원소들은 각각 인수와 지수의 관계를 맺고 있다. 따라서 리스트를 튜플의 리스트로 변환해서 처리하고, 최종적으로 튜플의 리스트를 다시 정수 리스트로 되돌리는 작업을 처리하는 함수들을 만들어보자.
list2tuples :: [a] -> [(a, a)]
list2tuples [] = []
list2tuples (a:b:xs) = (a,b):(list2tuples xs)
list2tuples _ = error "Invalid Input!!!"
tuples2list :: [(a, a)] -> [a]
tuples2list = concatMap t2l
where t2l (a, b) = [a, b]
어떤 정수 A, B를 표현하는 리스트를 각각 튜플의 리스트로 변환했다고 하자. 이 때 두 수의 최대 공약수는 어떻게 찾을까.
- 먼저 각각의 A, B를 표현하는 리스트를 튜플의 리스트로 변환한다.
- 우선 두 리스트에서 '인수'에 해당하는 부분만을 추려서 공통된 원소를 찾는다. 이는 두 수의 공통 소인수이다.
- 1.에서 찾은 각각의 공통 소인수에 대해 A에 대해서 그 지수값을 찾는 함수를 작성한다.
- 2의 함수를 A, B에 대해 적용하고 그 중 작은 값을 취하면 GCD에서의 해당 소인수의 지수가 된다.
- 2의 소인수 리스트에 대해 3을 맵핑해주고, 그 결과를 취합한다.
- 취합된 결과를
tuples2list에 넣어서 리스트로 만들어주면 된다.
그런데 우리는 N 개의 수를 가지고 있다고 했다. 세 수 A, B, C의 최대 공약수를 구할 때, 먼저 A, B의 최대공약수를 구한다. 이 값과 C의 최대공약수를 구하면 세 수의 최대공약수가 된다. 따라서 N개의 수에 대한 최대 공약수는 최대 공약수를 구하는 함수를 이용해서 수들의 리스트를 접으면(!) 된다.
최대 공약수(?)를 구하기
최대 공약수를 구하는 함수에 대한 설명은 위에 있으니, 그에 대한 구현을 만들어보자. 우선 이 함수의 타입을 보면 [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] 타입이 된다. 튜플의 리스트 2개를 받아서 공약수를 구성하는 인수와 지수를 만들어 주면 되는 것이다. 이 이름을 myGCD라고 하자.
myGCD :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
myGCD xs ys = ...
먼저 두 수(?) xs, ys에서 공통 인수를 뽑아보자. 공통 인수는 xs, ys를 각각 map fst 하여 인수만 취한 다음 intersect를 통해서 공통집합을 구하면 된다. intersect는 Data.List에 포함되어 있다.
참고로 하스켈에서는 intersect, union, \\ 등과 같은 집합 연산이 모두 리스트에 대해서 효율적으로 구현되어 있다. (즉 순서없는 집합을 특별히 쓰지 않는 것 같다.)
그런데 두 인수에 대해서 같은 처리를 한 다음에 intersect를 해야 하는 상황, 어디서 본 것 같지 않나? on 함수가 등장할 차례이다. 공통인수는 다음과 같이 구한다.
commonFactors = (intersect `on` map fs) xs ys
임의의 공통인수 c에 대해서 xs에서 그 지수를 찾는 함수를 작성해보자. 앞에서부터 인수가 아닌 걸 걸러내고, 인수를 찾으면 튜플의 두번째 요소를 취해야 한다. 이렇게 작성한다.
findE c = snd . head . dropWhile ((/= c) . fst)
자 이 함수가 무슨일을 하는지 보면
(/= c) . fst로 각 짝의 첫 요소가c와 다른 것들을 버린다.head로(c, e)인 원소를 찾았다.snd로 그 중에서 지수 값을 취했다.
그래서 공통인수 c 에서 xs, ys에 처리를 해서 min을 통해 그 중 작은 값을 구한다. 가만, 이거 또 앞에서랑 똑같은 패턴이지 않나? xs, ys는 고정된 값이므로 다음과 같이 1인자 함수로 정의한다. (이렇게하면 나중에 쓸 때 엄청 깔끔해진다.)
findMinE c = (min `on` findE c) xs ys :: Int
findMinE c 는 결국 c 인자의 작은 지수를 찾는 함수가 된다. 공통 인수들의 지수들은 결국 모든 공통인수에 대해서 이 함수를 적용하면 되므로 다음과 같이 구한다.
exps = map findMinE commonFactors
우리가 원하는 결과는 commonFactors와 exps의 결합이다. 이건 zip하면 되니까 최종적으로 myGCD는 아래와 같이 작성할 수 있다.
myGCD :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
myGCD xs ys = zip commonFactors exps
where
commonFactors = (intersect `on` map fst) xs ys
findE c = snd . head . dropWhile ((/= c) . fst)
findMinE c = (min `on` findE c) xs ys
exps = map findMinE commonFactors
자 이제 나머지는 입출력을 처리해야 하는 것만 남는다.
main = do
getLine -- n을 무시하자
contents <- (map (map read . words) . lines) <$> getContents
let result = tuple2list . foldr1 myGCD . map list2tuple $ contents
putStrLn . unwords . map show $ result
myGCD를 맨땅에 헤딩하는 마음으로 작성하는 것은 정말 쉽지 않았다. IDE가 있으면 좋겠다... (https://gist.github.com/stripe-q/b8fadb38d246b10d77539f3c595e8eea)