문제
암호화된 메시지를 복호화하라. 메시지 길이가 N일 때, R*C=N이고 R이 C 이하인 가장 큰 R을 찾아 R×C 격자에 열 우선으로 채운 뒤 행 우선으로 읽으면 원문이 된다.
입력
첫째 줄에 암호화된 메시지가 주어진다 (소문자, 길이 100 이하).
출력
복호화된 메시지를 출력한다.
예제
| 입력 | 출력 |
|---|---|
saleitwmtaos | sailormtweat |
풀이
메시지 길이로부터 R×C 격자 크기를 결정하고, 열 우선 채움 → 행 우선 읽기로 복호화한다.
- 메시지 길이 N의 약수 중 R이 C 이하를 만족하는 가장 큰 R을 찾는다
- C×R 배열에 메시지를 열 방향으로 순서대로 채운다
- 행 방향으로 읽어서 원문을 복원한다
핵심 아이디어: 암호화가 행→열 순서로 읽은 것이므로, 복호화는 열→행 순서로 채우고 행→열 순서로 읽으면 된다. N의 약수를 큰 것부터 찾아 R이 C 이하 조건에 맞는 첫 값을 사용한다.
코드
package com.ssafy.an.day049;
import java.util.Scanner;
public class Day10BOJ2999비밀이메일 { // 2999 비밀 이메일
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
String str = sc.nextLine();
int N = str.length();
int R = 0;
int C = 0;
for (int n = N; n > 0; n--) {
if (N % n != 0)
continue;
int c = n;
int r = N / c;
if (r > c)
break;
C = c;
R = r;
}
if (R == 0 && C == 0) {
R = 1;
C = 1;
} // 둘다 0일때.. 고려해야합니다..
char[][] arr = new char[C][R];
int s = 0;
for (int i = 0; i < C; i++) {
for (int j = 0; j < R; j++) {
arr[i][j] = str.charAt(s++);
}
}
for (int j = 0; j < R; j++) {
for (int i = 0; i < C; i++) {
sb.append(arr[i][j] + "");
}
}
System.out.println(sb);
sc.close();
}
}복잡도
- 시간: O(N) — 격자 채우기 및 읽기
- 공간: O(N) — R×C 격자 배열