먼저 각 단어가 후보인지 판별하고, 후보인 단어만 등장 횟수를 세면 된다. 여기서는 한 테스트 케이스를 다룬다. 을 와 모든 암호문 단어의 길이 중 최댓값이라고 하자.
보다 암호문 단어들이 먼저 입력되므로, 단어들을 저장한 뒤 를 읽는다. 단어 의 길이가 와 다르면 후보가 아니다. 길이가 같다면 크기가 인 두 배열을 새로 초기화한다. 첫 배열은 의 각 글자가 대응하는 의 글자를, 둘째 배열은 의 각 글자가 대응하는 의 글자를 기록한다.
같은 위치의 두 글자 를 차례로 확인한다. 이미 가 다른 글자에 대응하거나, 이미 가 다른 글자로부터 대응받고 있다면 를 제외한다. 그렇지 않으면 두 배열에 와 의 대응을 기록한다. 끝까지 모순이 없으면 후보이다. 각 단어의 대응은 독립적이므로 다음 단어를 검사할 때 두 배열을 다시 초기화한다.
후보의 실제 문자열을 키로 하는 정렬된 맵에 등장 횟수를 누적한다. 후보가 하나도 없으면 -1을 출력한다. 그렇지 않으면 등장 횟수가 가장 크고, 그중 사전순으로 가장 앞서는 키를 고른다. 동일한 치환 형태를 가지더라도 서로 다른 문자열은 따로 센다.
후보 판별에는 시간이 든다. 문자열 비교 한 번에 시간이 들므로 정렬된 맵을 사용한 전체 시간 복잡도는 , 공간 복잡도는 이다.
증명
어떤 유효한 치환으로 가 가 된다면 두 단어의 길이는 같다. 같은 평문 글자는 같은 암호문 글자로 바뀌므로 첫 배열에서 모순이 생기지 않는다. 서로 다른 평문 글자는 서로 다른 암호문 글자로 바뀌므로 둘째 배열에서도 모순이 생기지 않는다. 따라서 모든 후보는 판별을 통과한다.
반대로 판별을 통과했다면, 에 등장하는 각 글자는 정확히 하나의 암호문 글자에 대응하고 서로 다른 평문 글자의 대응 결과는 서로 다르다. 따라서 기록한 대응은 등장한 글자들 사이의 일대일 대응이다. 아직 대응을 정하지 않은 평문 알파벳과 사용하지 않은 암호문 알파벳의 개수는 같으므로, 이들을 임의로 일대일 대응시키면 전체 개 글자에 대한 유효한 치환을 완성할 수 있다. 이 치환은 를 정확히 로 바꾼다. 그러므로 판별을 통과한 단어는 모두 후보이다.
서브태스크 1에서는 모든 단어의 길이가 이므로 모든 암호문 단어가 후보이다. 크기 의 배열로 각 글자의 등장 횟수를 세고 답을 고르면 시간, 공간에 해결할 수 있다.
서브태스크 2에서는 길이가 같은 두 단어의 모든 위치 쌍 에 대해 와 의 참·거짓이 같은지 검사하는 방법으로 후보를 판별할 수 있다. 각 후보와 모든 입력 단어를 직접 비교하여 등장 횟수를 세면 시간 복잡도는 , 단어들을 저장하는 공간 복잡도는 이다.
각 입력 단어를 한 번씩 검사하여 후보인 경우에만 그 문자열의 횟수를 증가시키므로, 맵에는 각 후보의 정확한 등장 횟수가 저장된다. 가장 높은 횟수를 선택하고 동률일 때 사전순으로 가장 앞서는 단어를 선택하면 문제에서 요구한 추정 결과와 일치한다.
Solution written by GPT6
