백준 2999번 파이썬 코드 답안

문제

매일 밤, 정인이는 상근이에게 이메일을 보낸다. 정인이는 자신의 이메일이 해킹당할 수도 있다는 생각에, 내용을 항상 암호화해서 보낸다.

정인이가 사용하는 암호 알고리즘은 다음과 같다. 정인이가 보내는 메시지는 총 N글자이다.

먼저, 정인이는 R<=C이고, R*C=N인 R과 C를 고른다. 만약, 그러한 경우가 여러 개일 경우, R이 큰 값을 선택한다.

그 다음, 행이 R개고, 열이 C개인 행렬을 만든다.

이제 메시지를 행렬에 옮긴다. 첫 번째 행의 첫 번째 열부터 C번째 열까지 메시지를 순서대로 옮긴 뒤, 남은 메시지는 두 번째 행, 세 번째 행,... R번째 행에 첫 번째 행을 채운 방법과 동일한 순서대로 옮긴다.

행렬에 모두 메시지를 옮겼다면, 이 것을 첫 번째 열의 첫 번째 행부터 R번째 행까지 차례대로 읽으면서 다시 받아 적는다. 그 다음에, 두 번째 열, 세 번째 열,..., C번째 열에 쓰여 있는 문자를 첫 번째 열을 읽은 방법과 동일하게 받아적는다.

상근이는 매일 밤 정인이의 메시지를 해독하는데 지쳤다. 정인이의 암호 이메일이 주어졌을 때, 이를 해독하는 프로그램을 작성하시오.

입력

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

출력

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

문제 풀이 

아래 예시를 보면 문제가 어떤 내용인지 잘 알 수 있게된다. 정인이는 아래 그림과 같은 행렬을 만들고, 1행을 다 채우고, 2행으로 넘어가는 식으로 암호를 채운다. 그리고 실제로 암호를 보낼 때는 그 행렬을 세로 방향으로 읽어서 보낸다. 즉, 문제를 풀기 위해서 해야할 일은 R과 C가 어떤 값인지 찾아내고 원래의 암호를 기록하는 행렬을 만든다. 그리고 가로로 읽어서 보내면 된다.

먼저 r과 c를 찾는 것이다. R은 반드시 C보다는 작거나 같아야 한다는 점만 감안한다면, 결국 문자열의 전체 길이 중 딱 나눠 떨어지는 가장 큰 R을 찾으면 된다. 따라서, 문자열의 전체 길이 중 나눠 떨어질 때마다 r과 c값을 업데이트하면서, 조건에 맞는 r값을 구한다.

그리고 r에 대해서 리스트를 만든다. 리스트를 만든 후에는 행부터 하나하나씩 열을 채우는 방식으로 리스트를 복원한다. 리스트를 복원한 후, 행을 한번씩 읽어서 출력을 하게 되면 괜찮다.

시간을 좀 더 줄일 수 있을 것으로 생각되는 방법은 리스트를 만들지 않는 것이다. 예를 들어, r이 4라고 가정 한다면 문자열의 가장 첫번째 값을 출력하고, r의 배수를 더하면서 값을 출력 하는데 이것은 r이 전체 문자열의 길이를 넘지 않을 때까지 반복한다. 여기까지 완료되면 다시 한번 두번째 값을 출력하는 식으로 반복하는 것으로 접근이 가능할 것으로 보인다. 

import sys
my_str = str(sys.stdin.readline().rstrip())
r = 1
c = len(my_str)

for i in range(1,len(my_str)+1) :
    if len(my_str) % i == 0 :
        if r < i and i <= len(my_str) // i  :
            r = i
            c = len(my_str) // i

d = [[] for _ in range(r)]
cnt = 0

for i in range(c) :
    for k in range(r) :
        d[k].append(my_str[cnt])
        cnt +=1

for i in range(r) :
    print(''.join(d[i]), end='')