BOJ 5426 - 비밀 편지

문제

BOJ 5426 - 비밀 편지

길이가 완전제곱수인 문자열이 주어진다. 이 문자열을 n×n 행렬에 행 방향으로 채운 뒤, 열 방향으로 읽어 만든 메시지가 암호화된 편지다. 주어진 암호문을 복호화하여 원래 메시지를 출력한다.

입력

• 첫 줄: 테스트 케이스 수 T
• 각 테스트 케이스: 암호화된 문자열 한 줄 (길이는 완전제곱수)

출력

각 테스트 케이스마다 복호화된 원래 메시지를 출력한다.

예제

풀이

문자열을 n×n 행렬로 해석하여 열 방향으로 읽으면 원래 메시지가 복원된다. 열 우선 순서로 인덱스를 계산하여 문자를 수집한다.

1. 문자열 길이의 제곱근을 구해 행렬 크기 n을 결정한다.
2. 열 번호를 n부터 1까지 역순으로 순회하며, 해당 열의 모든 행 원소를 수집한다.
3. 인덱스 계산: i번째 열, j번째 위치 → j + (i-1)번째 원소 (1-based 행 간격 n으로 접근)
4. 수집한 문자를 이어 붙여 복호화된 메시지를 출력한다.

핵심 아이디어: 암호화는 행 우선으로 쓰고 열 우선으로 읽는 전치(transpose) 방식이다. 복호화는 반대로 열 번호를 기준으로 원본 인덱스를 역추적하면 된다.

코드

T = int(input())
 
for t in range(0, T):
    msg = input()
    n = int(len(msg) ** (1 / 2))
 
    decoded_msg = ""
    for i in range(n, 0, -1):
        for j in range(i, n * n + 1, n):
            decoded_msg += msg[j - 1]
 
    print(decoded_msg)

복잡도

• 시간: O(N)
• 공간: O(N)