제곱수를 나타내는 애너그램 쌍 찾기
단어 수는 2천 개도 안 되지만 각 단어의 알파벳을 임의의 수로 치환하는 경우의 수를 생각하면 엄청나게 많은 계산이 필요하다. 알파벳을 임의의 수로 치환하는 대신 제곱수를 미리 구해놓고 알파벳을 치환할 때 제곱수를 이용해 치환한다면 계산 범위를 크게 줄일 수 있다.
먼저 파일을 읽어 단어 목록을 만들고 애너그램을 구한다. 애너그램은 글자를 정렬했을 때 결과가 같으므로, 단어의 글자로 정렬한 결과를 키로 group-by하면 쉽게 애너그램을 구할 수있다.
(def words
(clojure.string/split (slurp "data/words.txt") #"\"(,\")?"))
(def anagrams
(->> words
(group-by (fn [w] (sort w)))
(filter (fn [[k ws]] (<= 2 (count ws))))
(map second)))
글자수와 같은 자리의 제곱수를 사용할 것이므로 다음과 같이 자릿수별 제곱수 맵을 만든다. 위에서 만든 애너그램에서 제일 긴 것이 9자로 되어 있으므로 제곱수도 9자리 숫자 ()까지 만들면 충분하다.
(def sqnums
(->> (iterate inc 1)
(map #(* % %))
(take-while #(< (Math/log10 %) 9))
(group-by #(inc (int (Math/log10 %))))
(map (fn [[k vs]] [k (set vs)]))
(into {})))
숫자 벡터를 숫자로 만드는 함수도 있으면 문제 풀이에 도움이 된다.
(defn digits-to-num [ds]
(loop [ds (reverse ds) p 1 n 0]
(if (seq? ds)
(recur (next ds) (* p 10) (+ n (* (first ds) p)))
n)))
문제를 풀려면, 단어에 있는 알파벳을 숫자로 치환한 다음 동일한 규칙을 애너그램에 적용했을 때 역시 제곱수가 되는지 확인하는 코드를 작성해야 한다.
다음 함수는 주어진 단어에 대해 제곱수로 바꾸는 규칙을 담은 맵을 생성해 리턴한다. 이 함수가 리턴한 맵을 이용해 동일한 규칙으로 애너그램을 숫자로 치환해 제곱수가 되는지 확인할 것이다. 알파벳을 숫자로 치환할 때 알파벳이 같으면 치환하는 숫자도 같아야 한다. 또한 다른 알파벳은 다른 수로 치환해야 한다.
(defn w->sqns [w]
(letfn [(same-letters-have-same-digit? [m]
(= 1 (->> (group-by first m)
(map (fn [[_ v]] (count (distinct v))))
(apply max))))
(diff-letters-have-diff-digits? [m]
(= 1 (->> (group-by second m)
(map (fn [[_ v]] (count v)))
(apply max))))]
(->> (for [n (sqnums (count w))] (map vector w (digits n)))
(filter same-letters-have-same-digit?)
(filter diff-letters-have-diff-digits?)
(map (fn [x] (into {} x)))))
애너그램 쌍이 제곱 에너그람 쌍인지 확인하는 함수는 다음과 같이 작성할 수 있다. w->sqns 함수로 구한 치환 규칙을 애너그램에 적용해 역시 제곱수가 되는지 확인한다.
(defn check [[w1 w2]]
(let [sqns (sqnums (count w1))
ms (w->sqns w1)
ns (for [m ms] (digits-to-num (map #(m %) w2)))]
(filter #(contains? sqns %) ns)))
이제 문제를 다음과 같이 풀 수 있다.
(defn solve []
(->> anagrams
(map #(check %))
(remove empty?)
(flatten)
(apply max)))
실행 결과는 다음과 같다. 답을 구하는 데 1초 조금 넘게 걸린다.
p098> (time (solve)) "Elapsed time: 1037.136248 msecs" 18?69