[HackerRank]加密(Encryption)

題目描述

一串英文文字必須被使用以下的方式來加密。

首先,文字中所有的空格字元都要被移除。假設L為文字的長度,然後把每個字元排列成棋盤的形狀,棋盤的列和欄有以下的約束:

⌊√L⌋ ≤ 列 ≤ 欄 ≤ ⌈√L⌉

上式中,⌊x⌋為x無條件捨去小數的結果;⌈x⌉為x無條件進位的結果。

舉例來說,這個句子「if man was meant to stay on the ground god would have given us roots」移除掉空格之後共有54個字元,所以它可以寫成如下的7列8欄之棋盤形狀:

ifmanwas
meanttos
tayonthe
groundgo
dwouldha
vegivenu
sroots

必須確認

列 * 欄 ≥ L

若有許多棋盤大小符合以上的條件,選擇面積最小的那個。

編碼之後的訊息為棋盤文字從左到右與從上到下的重新排列結果,每欄之間要用空格字元分隔。舉例來說,以上棋盤文字編碼之後,得到的文字為:

imtgdvs fearwer mayoogo anouuio ntnnlvt wttddes aohghn sseoau

您將會得到一個由英文組成的文字訊息,沒有空格。訊息最長的長度為81個字元。請輸出編碼之後的文字。

原題網址

https://www.hackerrank.com/challenges/encryption

範例輸入1

haveaniceday

範例輸出1

hae and via ecy

範例輸入2

feedthedog

範例輸出2

fto ehg ee dd

範例輸入3

chillout

範例輸出3

clu hlt io

解題概念

列數和欄數相乘的結果要大於等於文字長度。首先要計算棋盤形狀的列數和欄數,由於這兩數一定要是整數,所以在開根號計算後會有進位問題。欄比列大,可以先計算欄的數量為⌈√L⌉。至於為什麼不是用⌊√L⌋來計算呢?因為當√L*√L=L時,若其中一個運算子變小了,那另外一個運算子就一定要變大,這樣欄就會比列小了。現在有了欄的數量C,所以列的數量就為L除C,由於除法可能會無法整除,且為了讓欄乘以列的值大於等於文字長度,因此列的值為⌈L/C⌉。

知道棋盤形狀的列數和欄數後,接著要將原始文字儲存至這個棋盤形狀中,再從左到右與從上到下重新排列後輸出。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章