서론
백준 문제를 풀려고 보다가 많이 제출하지 않은 이 문제를 보고 홍대병이 도져서 꼭 정복하고 싶다는 생각이 들어서 풀게 되었다.
문제를 살펴보자.
(사실 초반에 해맸는데 해석이 많지 않아 본인과 같은 사람이 있을까 싶어 작성한다.)
문제
어떤 문장을 키를 이용하여 다음과 같이 암호화하려 한다. 암호화하기 전의 문장을 평문이라 하며, 암호화 된 문장은 암호문이라고 한다. 키, 평문, 암호문은 모두 영어 대문자로 된 공백 없는 문장이다.
키의 길이를 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 가 된다.
키와 암호문이 주어졌을 때, 이를 이용하여 평문을 구하는 프로그램을 작성하시오.
문제 해석
처음에 문제를 보고 오 키와 평문으로 암호문을 구하는 문제구나 했다가 틀렸다.
문제를 잘 읽어보는 것이 중요하겠다. 우선 키가 어떻게 정렬이 되는지 알아보자.
BATBOY -> ABBOTY
이렇게 변경이 된 것으로 보아 알파벳 순으로 정렬이 되었음을 확인할 수 있다.
그렇다면 알파벳 순으로 정렬이 된 이런 빈 테이블에 입력받을 예정인 암호문을 (EYDEMBLRTHANMEKTETOEEOTH)
| A | B | B | O | T | Y |
|---|---|---|---|---|---|
첫 번째 열부터 빈칸 없이 채워 준 뒤에, (암호문/키의 길이 로 열에 몇개의 데이터가 들어가는지 유추가능)
| 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 |
원래의 키 순서대로(BATBOY) 조합 한 후에, 첫 번째 행 부터 출력 하면 된다.
| B |
|---|
| M |
| B |
| L |
| R |
+
| A |
|---|
| E |
| Y |
| D |
| E |
+
| T |
|---|
| E |
| T |
| O |
| E |
+
| B |
|---|
| T |
| H |
| A |
| N |
+
| O |
|---|
| M |
| E |
| K |
| T |
+
| Y |
|---|
| E |
| O |
| T |
| H |
=
| 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 |
거추장스럽게 말했지만 결국 거꾸로 하면 된다는 이야기이다. ☠️
코드
주의 ! 효율적인 코드가 아닙니다. 참고용 예시로만 보길 권장합니다.
import sys
key = sys.stdin.readline().rstrip('\n') # 키를 입력 받습니다.
encoded_text = sys.stdin.readline().rstrip('\n') # 암호화 된 문장을 입력 받습니다.
lines = len(encoded_text) // len(key) #
sort_key = sorted(key) # 알파벳 순으로 키를 정렬합니다.
decoded_dict = dict() # 사람 보기 좋으라고 딕셔너리 생성
for i in range(len(key)):
# 사람 보기 좋으라고 몇 번째 인덱스에 어떤 문자 + 그 문자와 같은 인덱스 였던 문자들을 합쳐줍니다.
# 다시 한다면 그냥 list 에 넣고 enumerate 로 찍어 보고 말았을 것 같군요..
decoded_dict[i] = sort_key[i] + encoded_text[lines*i:lines*(i+1)]
# 딕셔너리에 넣은 값 중 value 값만 따로 빼서 리스트로 저장합니다.
values = list(decoded_dict.values())
# 얘도 위에서 선언한 딕셔너리와 같은 이유 입니다..
plain_dict = dict()
for i in range(len(key)):
for j in range(len(values)):
if key[i] == values[j][0]: #딕셔너리로 저장해놓은 값의 앞 글자와 키의 앞 글자가 같다면,
plain_dict[i] = values.pop(j) #키에 같은 알파벳이 있을 수 있으니 리스트에서 값을 제거하여 plain_dict 에 넣고
break # 다음 키에 대해 맞는 값을 찾도록 가장 안쪽 반복문을 탈출합니다.
for i in range(1, lines+1): # 첫 번째 값에 사람 보기 좋으라고 키의 알파벳을 넣어 놨으니 1부터 시작해서
for j in list(plain_dict.values()):
print(j[i], end='') # 이전 반복문에서 원래 순서대로 정리한 값을 출력합니다.결론
사실 코드를 고쳐서 더 효율적으로 만든 뒤 포스팅 하려고 했지만
