[google codejam 2019 QR] Cryptopangrams

문제 설명

구글 코드잼 2019년 QR 세번째 문제 Cryptopangrams

팬그램(pangram)이라는 용어가 나옵니다.

팬그램은 알파벳 A부터 Z까지를 적어도 한번씩은 모두 사용해서 만든 문구를 의미합니다.

문제는 팬그램을 구성하는 알파벳 26개에 솟수(prime number)를 하나씩 대응시키는 것으로 시작됩니다(솟수는 A부터 Z까지 오름차순으로 부여합니다. 즉, A에 대응하는 솟수는 다른 모든 알파벳에 대응하는 솟수보다 클 수 없음. 마찬가지로 Z에 대응하는 솟수가 제일 큼)

예를 들어서 H, E, L, O에 아래와 같이 솟수를 대응시키고

E(19), H(23), L(43), O(101), ....

길이가 N인 팬그램이 `HELLO...`로 시작된다면아래와 같이 인접한 알파벳에 대응하는 솟수끼리 곱해서 N-1개의 암호숫자를 만들 수 있습니다.

H: 19

E: 23 => 19*23 = 437

L: 43 => 23*43 = 989

L: 43 => 43*43 = 1849

O: 101 => 43*101 = 4343

((나머지 팬그램 구문 생략))

437 989 1849 4343 ... 

* 길이 N인 pangram에 대해서 길이 N-1의 암호 숫자를 만들 수 있습니다.

* 암호숫자의 최대 길이는 100자리입니다

입력으로 길이 L(길이 N-1)인 암호 숫자가 주어지면 이를 통해서 역으로 길이 N인 원래의 pagram을 구해서 출력합니다.

입력

테스트케이스는 두가지로 주어집니다.

알파벳 26개에 대응시킬 수 있는 솟수의 범위가 10000이하인 small케이스와 10¹⁰⁰(101자리) 이하인 large케이스로 나뉩니다.

풀이

small case

small 케이스에 대해서는 10000 이하의 솟수 1229개를 미리 모두 구한 후 주어진 암호숫자 C 가 나누어 떨어지는 솟수를 구하면 평문 pagram을 찾아낼 수 있습니다.(주어진 암호숫자들은 두 솟수의 곱이기때문에 인수factor는 1229개 중에 하나).

* 1229개 솟수를 오름차순으로 담은 배열에 대해서 이진 탐색을 하면 최대 11회만에 암호숫자의 소인수를 구할 수 있습니다(하지만 솟수의 갯수가 많지 않기때문에 순차 탐색으로 구현해도 문제는 없음)

* 무식한 방법으로는 1229*1229 의 모든 곱셈 조합 151만개를 모두 구해놓고 hashmap 에 {key:암호숫자, value:[솟수1, 솟수2]} 와 같이 담아서 곧바로 찾을 수도 있습니다. 서로다른 4개의 솟수 a, b, c, d에 대해서 2개씩 묶어서 곱할 경우 (예를 들어 a*b, c*d) 이 두 값이 같은 경우는 없으므로 암호숫자와 솟수pair 는 1:1 대응됩니다.

large case

large 케이스는 알파벳마다 100자리 솟수를 대응시킬 수 있기 때문에 수많은 솟수를 메모리에 담아서 검색하는 것은 사실상 불가능합니다(100자리까지의 솟수를 구하다 20초 지날듯).

솟수를 일일이 곱해서 확인하는 접근 방식은 더이상 통하지 않으므로 문제를 다른 각도에서 살펴봅니다.

주어진 L개의 암호숫자 각각을 C라고 하고, L+1개(N개)의 솟수들을 P_i라고 하면(0 <= i <= L) C는 아래와 같이 두개의 솟수로 구성됩니다.

P₀ * P₁ = C₁

P₁ * P₂ = C₂

...

P_i-1 * P_i = C_i

P_i * P_i+1 = C_i+1

...

P_L-1 * P_L = C_L

매우 큰 하나의 암호숫자에 대해서 소인수 2개를 구하는 것은 힘들지만 문제의 규칙으로 생성된 인접한 두 개의 암호 숫자C_i, C_i+1에 대해서는 공통의 인수 P_i를 찾는 것은 어렵지 않습니다.

P_i-1    P_i   P_i+1
     C_i   C_i+1

인터넷이 흔하게 널려있는 최대 공약수 구하는 알고리즘을 Ci와 Ci+1 적용하면 두 수의 최대 공약수인 솟수 Pi를 구할 수 있고, 

P_i-1 = C_i / P_i

P_i+1 = C_i+1 / P_i

위와 같이 나머지 두 개의 솟수도 특정할 수 있습니다.

AAA..., ABA...

하지만 이 문제의 복병은 원문 pagram이 아래와 같은 패턴으로 주어지는 경우 위의 알고리즘으로는 모든 Pi를 특정할 수 없는데 있습니다.

BXBXB... => B*X와 X*B는 동일한 암호숫자들

AAA... => A*A로 동일한 암호숫자가 생성됨

인접한 암호숫자 Ci와 Ci+1이 똑같다면(그리고 이 패턴이 맨 처음 등장한다면) 두 숫자의 최대 공약수는 Pi가 아닌 자기 자신이기때문에 Pi-1과 Pi+1도 특정할 수 없습니다.

위에 설명한 알고리즘은 ABC, AAB, ABB와 같이 3개 솟수(알파벳)가 서로 다른 2개의 암호숫자를 생성할때는 올바로 작동하지만 AAA.. 나 ABA.. 패턴과 같이 2개의 암호숫자값이 똑같을때는 작동하지 않습니다.

원문 pagram의 특성상 이런 반복 패턴은 어디에선가는 깨집니다. 모든 알파벳을 전부 사용하기때문에 ABC, AAB, ABB패턴이 등장하는 곳에서부터(즉 서로다른 암호숫자 2개가 등장하는 곳에서부터) 위의 알고리즘을 적용하면 연쇄적으로 AAA..., ABA... 패턴들에 대해서도 해결 가능합니다.

A0, A1, A2, A3, B4 => C1 C2 C3 C4, (C1=C2=C3, but C3 != C4)

위와같이 암호숫자의 처음부터 C1, C2, C3, C4가 주어질때 인접한 암호숫자가 동일한 경우는 일단 건너뜁니다.

   C1 C2 C3 C4 - skip
   ^  ^

C1과 C2는 같으므로 건너뜀. C2 C3 비교

   C1 C2 C3 C4 - skip
      ^  ^

C2과 C3도 같으므로 건너뜀. C3 C4 비교

   C1 C2 C3 C4 - solve!
         ^  ^

C3과 C4는 서로 다름. 알고리즘을 전개해서 P₂, P₃, P₄를 특정함

P₂를 특정했으므로 P₁을 특정할 수 있습니다.( P₁ = C₂ / P₂)

P₁을 특정했으므로 P₀을 특정할 수 있습니다.(P₀ = C₁/P₁)

일반화

주어진 L개의 암호 숫자에 대해서 서로 다른 인접한 암호숫자 C_i와 Ci_i+1로부터 [P_i-1, P_i, P_i+1] 을 특정하면 연쇄적으로 좌우방향으로 나머지 솟수들을 특정할 수 있습니다.