2149번: 암호 해독

문제 출처 : https://www.acmicpc.net/problem/2149

 

언어 : Kotlin

 

문제 설명 :

어떤 문장을 키를 이용하여 다음과 같이 암호화하려 한다. 암호화하기 전의 문장을 평문이라 하며, 암호화 된 문장은 암호문이라고 한다. 키, 평문, 암호문은 모두 영어 대문자로 된 공백 없는 문장이다.

 

키의 길이를 N이라고 했을 때, 우선 평문을 N 글자씩 잘라서 다음과 같이 나열한다. 예를 들어 평문이 MEETMEBYTHEOLDOAKTREENTH 이고, 키가 BATBOY라고 해 보자.

 

B	A	T	B	O	Y
M	E	E	T	M	E
B	Y	T	H	E	O
L	D	O	A	K	T
R	E	E	N	T	H

 

제일 윗줄은 이해를 돕기 위해 키를 다시 한 번 쓴 것이다. 이제 이 행렬(배열)을 열(Column) 단위로 정렬을 하는데, 정렬을 하는 키준은 키의 문자로 한다. 즉 BATBOY를 정렬하여 ABBOTY와 같이 정렬하는 것이다. B와 같이 여러 번 나타나는 문자의 경우에는 원래의 행렬에서 더 왼쪽에 있었던 것을 먼저 쓴다. 정렬을 한 행렬은 다음과 같다.

 

A	B	B	O	T	Y
E	M	T	M	E	E
Y	B	H	E	T	O
D	L	A	K	O	T
E	R	N	T	E	H

 

B는 두 가지가 있기 때문에 더 왼쪽에 있었던 (B)MBLR이 먼저 나왔다. 이제 이와 같이 정렬한 행렬을 열 번호가 작은 것 먼저, 열 번호가 같다면 행 번호가 작은 것 순으로 나열하면 암호문이 된다. 즉 위와 같은 경우의 암호문은 EYDEMBLRTHANMEKTETOEEOTH 가 된다.

 

키와 암호문이 주어졌을 때, 이를 이용하여 평문을 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 키가 주어지고, 둘째 줄에 암호문이 주어진다. 키와 암호문은 모두 영어 대문자로만 되어 있으며, 암호문의 길이가 항상 키의 길이의 배수라고 하자. 키의 길이는 10자 이하이며 암호문의 길이는 100자 이하이다.

 

출력 :

첫째 줄에 평문을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
HUMDING EIAAHEBXOIFWEHRXONNAALRSUMNREDEXCTLFTVEXPEDARTAXNAARYIEX	ONCEUPONATIMEINALANDFARFARAWAYTHERELIVEDTHREEBEARSXXXXXX

 

풀이 : 

문제에서 주어진 평문과 Key를 이용해 암호문을 만드는 방법을 역으로 행하면 된다.

암호문을 평문으로 돌리기 위해 평문을 암호문으로 만든 것과 동일하게 Key를 기준으로 열 정리를 해야한다.

 

Key를 기준으로 만들기 위해 key를 인덱스와 같이 저장할 map을 만들고, 이를 사전순으로 정렬한다.

이후, Key의 길이만큼씩 나눠 담을 array에 정렬된 키를 기준으로 나누어 담는다.

 

열들을 정렬 전으로 되돌렸으니 각 행을 순서대로 읽으면 평문이 나오게 된다.

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val key = readLine()
    val password = readLine()

    val standard = key.mapIndexed { index, c -> Pair(c, index) }.sortedBy { it.first }
    val rows = password.length / key.length
    val columns = Array(key.length) { CharArray(rows) }

    var idx = 0
    for ((_, i) in standard) {
        for (r in 0 until rows) {
            columns[i][r] = password[idx++]
        }
    }

    val plainText = StringBuilder()
    for (r in 0 until rows) {
        for (c in key.indices) {
            plainText.append(columns[c][r])
        }
    }

    bw.write(plainText.toString())
    bw.flush()
    bw.close()
}