[BOJ/2999] 비밀 이메일 (Feat. 정말 좋은 2차원 리스트 연습문제)

문제 설명

매일 밤, 정인이는 상근이에게 이메일을 보낸다. 정인이는 자신의 이메일이 해킹당할 수도 있다는 생각에, 내용을 항상 암호화해서 보낸다.
정인이가 사용하는 암호 알고리즘은 다음과 같다. 정인이가 보내는 메시지는 총 N글자이다.
먼저, 정인이는 R<=C이고, R*C=N인 R과 C를 고른다. 만약, 그러한 경우가 여러 개일 경우, R이 큰 값을 선택한다.
그 다음, 행이 R개고, 열이 C개인 행렬을 만든다.
이제 메시지를 행렬에 옮긴다. 첫 번째 행의 첫 번째 열부터 C번째 열까지 메시지를 순서대로 옮긴 뒤, 남은 메시지는 두 번째 행, 세 번째 행,... R번째 행에 첫 번째 행을 채운 방법과 동일한 순서대로 옮긴다.
행렬에 모두 메시지를 옮겼다면, 이 것을 첫 번째 열의 첫 번째 행부터 R번째 행까지 차례대로 읽으면서 다시 받아 적는다. 그 다음에, 두 번째 열, 세 번째 열,..., C번째 열에 쓰여 있는 문자를 첫 번째 열을 읽은 방법과 동일하게 받아적는다.
상근이는 매일 밤 정인이의 메시지를 해독하는데 지쳤다. 정인이의 암호 이메일이 주어졌을 때, 이를 해독하는 프로그램을 작성하시오.

입력
첫째 줄에 상근이가 받은 메시지가 주어진다. 이 메시지는 알파벳 소문자로만 이루어져 있고, 최대 100글자이다.

출력
첫째 줄에 상근이가 받은 메시지를 해독한 메시지를 출력한다.

2999번 문제는 약수 개념과 2차원 리스트를 다루는 법을 배우기 아주 좋은 문제입니다. 한 번 풀어봅시다.

문제 해결

먼저, 입력으로 인코딩이 된(명시된 규칙으로 암호화 된) 문자열이 주어집니다.

암호화 과정을 알기 때문에 디코딩(복호화)하여 문자열을 출력하면 됩니다. 우선, 인코딩 과정을 한 번 살펴봅시다.

인코딩 과정

1. 문자열이 존재한다. 해당 문자열의 약수 중 조건에 부합하는 R, C 값을 구한다.
2. R * C 행렬을 생성해 문자열을 순서대로 삽입한다. (첫번째 행의 첫번째 열부터 C번째 열까지 순서대로)
3. 그렇게 생성한 문자열 행렬의 첫번째 열의 첫번째 행부터 R번째 행까지 하나의 행으로 만들어 C*R 행렬에 순서대로 삽입한다.
4. 그렇게 생성한 C개의 행을 순서대로 나열해 하나의 문자열로 만든다.

 자, 그럼 위 인코딩 과정을 반대로 진행하면 원래의 문자열을 유추할 수 있겠죠?

그렇다면 다음과 같은 순서로 원래의 문자열을 구합니다.

• R, C 값 구하기
• 최종적으로 생성된 문자열은 R개의 글자로 이루어진 문자열이 C개 있는 문자열이니 전체 문자열을 C개의 부분 문자열로 만들기
• 그렇게 만든 부분 문자열을 2차원 리스트에 넣어(그림에서 오른쪽 행렬 그림) 원래 문자열 구하기

약수 구하기(Python)

약수란 무엇일까요? 어떤 수를 특정 수로 나누었을 때 나누어 떨어지는 경우에 그 특정수를 어떤 수의 약수라고 칭합니다.

36이라는 수의 약수는 무엇이 있을까요? 1, 2, 3, 4, 6, 9, 12, 18, 36 이 있습니다.

 그렇다면 어떻게 파이썬을 사용해 약수를 구할 수 있을까요?

36이라는 수의 약수를 구하기 위해선, 1부터 36까지 반복문(i로 지칭)을 돌며 36이라는 수를 i로 나눴을 때 나눠 떨어지는지 확인하면 됩니다.

n = int(input()) # 36
divs = [] # 약수가 담길 배열을 의미

for i in range(1, n + 1):
	if n % i == 0:
    	divs.append(i)
        
print(divs) # [1, 2, 3, 4, 6, 9, 12, 18, 36]

이제 약수 배열을 구했으니 여기서 R과 C를 추출해봅시다.

R값은 C보다 작거나 같아야 하며 R값은 R값의 후보 중 가장 큰 값이어야 합니다.

R값과 C값의 후보 순서쌍은 다음과 같아집니다.

(1, 36) (2, 18), (3, 12), (4, 9), (6, 6)

약수 배열의 대칭성을 이용해 조건을 만족하는 R값은 배열의 가운데 값이 될 것입니다. 단, 배열의 길이가 짝수이냐 홀수이냐에 따라 달라집니다. 예를 들어 28이라는 수의 R,C 순서쌍은 다음과 같을 것입니다.

(1, 28) (2, 14), (4, 7)

이제, R과 C를 특정하는 코드를 작성해보겠습니다.

if len(divs) % 2 == 0:
    # 약수 배열의 길이가 짝수인 경우
    r = divs[len(divs) // 2 -1]
else:
    # 약수 배열의 길이가 홀수인 경우
    r = divs[len(divs) // 2]

c = n // r

---

문자열 자르기

R과 C를 구했으니 이제 R의 길이를 가진 C개의 부분 문자열을 2차원 리스트에 담아봅시다. 코드를 참조해주세요!

s = input()
n = len(s)
divs = []

for i in range(1, n+1):
    if n % i == 0:
        divs.append(i)

if len(divs) % 2 == 0:
    # 약수 배열의 길이가 짝수인 경우
    r = divs[len(divs) // 2 - 1]
else:
    # 약수 배열의 길이가 홀수인 경우
    r = divs[len(divs) // 2]
c = n // r

# 이 위의 코드들은 위에서 다룬 내용을 다듬은 코드입니다.
mat = list('' for _ in range(c))

for i in range(c):
    mat[i] = list(s[:r])
    s = s[r:]

디코드하기

자, 이제 C*R 행렬에서 첫번째 열의 첫번째 행부터 마지막 행까지 문자열을 추출합니다. 그 과정을 첫번째 열부터 마지막 열까지 진행해 초기 문자열을 얻어냅니다.

for i in range(r):
    for j in range(c):
        print(mat[j][i], end="")

결과

s = input()
n = len(s)
divs = []

for i in range(1, n + 1):
    if n % i == 0:
        divs.append(i)

if len(divs) % 2 == 0:
    # 약수 배열의 길이가 짝수인 경우
    r = divs[len(divs) // 2 - 1]
else:
    # 약수 배열의 길이가 홀수인 경우
    r = divs[len(divs) // 2]

c = n // r

mat = list("" for _ in range(c))

for i in range(c):
    mat[i] = list(s[:r])
    s = s[r:]

for i in range(r):
    for j in range(c):
        print(mat[j][i], end="")

참고자료

https://www.acmicpc.net/problem/2999