2999번: 비밀 이메일

문제

정인이가 상근이에게 비밀 이메일을 보내려고 합니다. 비밀 이메일을 보내는 암호화 방법은 다음과 같습니다.

1. 메시지의 전체 글자 수 N을 구합니다.
2. R <= C 이고 R * C = N을 만족하는 양의 정수 R과 C를 고릅니다. 만약 그러한 경우가 여러 개라면 R이 가장 큰 값을 선택합니다.
3. R행 C열의 2차원 배열(행렬)을 만들고, 메시지를 열 단위로 순서대로 적어 내립니다.
4. 다 적은 후에는 배열을 행 단위로 읽어서 암호화된 메시지를 만듭니다.

상근이가 받은 암호화된 메시지가 주어졌을 때, 이를 원래의 메시지로 복호화(해독)하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 암호화된 메시지가 주어집니다. (길이는 최대 100, 알파벳 소문자로만 구성)
• 출력: 첫째 줄에 해독된 원래의 메시지를 출력합니다.

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

풀이: 2차원 배열을 활용한 역순 복호화 시뮬레이션

암호화 과정을 정확히 반대로 거슬러 올라가는 복호화 시뮬레이션 방식입니다. 행렬의 크기를 정하는 수학적 최적화와 2차원 배열의 행/열 인덱스 접근이 이 문제의 핵심입니다.

• R과 C 찾기: 반복문(for)을 1부터 문자열 길이(N)의 제곱근(i * i <= s.length())까지만 순회합니다. 문자열의 길이로 나누어 떨어지는 수 중 가장 마지막으로 찾은 수(i)가 조건을 만족하는 가장 큰 R이 되며, 그에 짝지어지는 몫이 C가 됩니다.
• 배열 할당 및 채우기 (암호화의 역순): 암호화 과정에서 $R \times C$ 배열에 '열' 단위로 적고 '행' 단위로 읽어냈으므로, 복호화 과정에서는 반대로 $C \times R$ 크기의 2차원 배열(a)을 생성한 뒤, 입력받은 문자열을 '행' 단위로 가로로 쭉 채워 넣습니다. 인덱스를 활용하여 a[i / r][i % r] 위치에 문자를 순차적으로 삽입합니다.
• 열 단위 읽어내기: 배열을 모두 채운 후, 바깥쪽 반복문을 r로, 안쪽 반복문을 c로 설정하여 '열' 단위로 세로로 읽어내어 StringBuilder에 덧붙입니다 (sb.append(a[j][i])). 이를 통해 암호화되기 전의 원래 메시지가 완벽하게 복원됩니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       String s = br.readLine();
       int r = 1, c = s.length();
       
       // R <= C 이고 R * C = N 인 가장 큰 R 찾기 (제곱근 탐색 최적화)
       for (int i = 1; i * i <= s.length(); i++) {
          if (s.length() % i == 0) {
             r = i;
             c = s.length() / i;
          }
       }

       // C x R 크기의 배열에 행 단위로 암호문 채우기
       char[][] a = new char[c][r];
       for (int i = 0; i < s.length(); i++) {
          a[i / r][i % r] = s.charAt(i);
       }

       // 열 단위로 읽어서 원래 메시지 복원
       StringBuilder sb = new StringBuilder();
       for (int i = 0; i < r; i++) {
          for (int j = 0; j < c; j++)
             sb.append(a[j][i]);
       }

       bw.write(sb.toString());

       bw.flush();
    }
}

알고리즘 분류

구현 (Implementation), 문자열 (String)