[소프티어] 플레이페어 암호 자바 풀이 시간초과 해결 완료 (HSAT 3회 정기 코딩 인증평가 기출)
https://softeer.ai/practice/6255
Softeer - 현대자동차그룹 SW인재확보플랫폼
softeer.ai
| JavaScript | 1초 | 1024MB |
| C | 1초 | 1024MB |
| C++ | 1초 | 1024MB |
| Java | 1초 | 1024MB |
| Python | 2초 | 1024MB |
대학교 학부생활을 마치고 현대자동차에 프로그래머로 취직한 사회초년생 현빈이는 팀장님에게 보안에 관련한 지식이 하나도 없음을 들키고 말았다. 그래서 현빈이는 업무시간 틈틈이 보안과 관련된 주제들을 공부하고 있다.
오늘 공부할 주제는 암호화 방식중 하나인 Playfair cipher(플레이페어 암호)다. Playfair cipher는 알파벳으로 이루어진 어떤 문자열(평문; plaintext)을 암호화하는 방법으로, 이를 위해 알파벳으로 이루어진 문자열인 키(key)가 필요하다. Playfair cipher는 빈도분석을 어렵게 하기 위해 한번에 두 글자 단위로 암호화를 진행하며, 5×5크기의 표를 사용하기 때문에 알파벳 26개를 모두 담기에는 칸이 한 개 부족해 I와 J를 동일한 것으로 생각한다. 이 문제에서는 편의상 J가 아예 주어지지 않는다.
먼저, 주어진 키를 5×5크기의 표로 변환한다. 키를 한 글자씩 보면서 왼쪽 위 칸부터 한줄씩 표를 채운다. 만약 이전에 봤던 알파벳이 한번 더 등장하면 무시하고 다음 글자를 보면 된다. 키를 다 보고도 칸이 남는다면, 아직 등장하지 않은 알파벳을 순서대로 채워넣으면 된다. 예를 들어 키가 PLAYFAIRCIPHERKEY라면 다음과 같이 표가 만들어진다. 굵게 표시된 알파벳이 키를 통해 채워진 알파벳이다.
다음 일은 암호화하려는 메세지를 두 글자씩 나누는 일이다. 예를 들어, HELLOWORLD라는 메세지를 두 글자씩 나눈다면 HE LL OW OR LD가 된다. LL같이 두 글자로 이루어진 쌍이 생기면 중간에 다른 글자를 넣어 쌍을 파괴해줘야 한다. 이렇게 같은 두 글자로 이루어진 쌍이 생기면 그 중 가장 앞에 있는 쌍 사이에 X를 넣고 뒤쪽은 새롭게 쌍을 구성하면 된다. 만약, 쌍이 XX였다면 X를 넣어서는 해결이 안되기 때문에 Q를 넣는 것으로 해결 한다. 이렇게 쌍을 모두 맞추고 마지막에 한 글자가 남는다면 이것도 암호화가 불가능하기 때문에 여기도 X를 덧붙여 강제로 쌍을 맞춰준다. 마지막 남은 한 글자가 X인 경우에는 예외적으로 XX로 쌍을 맞춘다.
그러므로, HELLOWORLD를 두 글자씩 나누는 올바른 방법은 HE LX LO WO RL DX이고, XXYYY를 두 글자씩 나누는 올바른 방법은 XQ XY YX YX가 된다. 마지막으로, 쌍을 만든 두 글자를 암호화하는 일이 남았다. 다음과 같은 세 가지 경우가 있는데, 위에서 만든 5×5표를 통해 설명해본다.
1. 만약, 두 글자가 표에서 같은 행에 존재하면, 오른쪽으로 한 칸 이동한 칸에 적힌 글자로 암호화된다. 예를 들어 HE를 암호화하면 EI가 되고, XX를 암호화하면 ZZ가 된다. 위치가 다섯 번째 열이라면 첫 번째 열로 이동하게 된다.
2. 1.의 경우를 만족하지 않으면서 두 글자가 표에서 같은 열에 존재하면, 아래쪽으로 한 칸 이동한 칸에 적힌 글자로 암호화된다. 예를 들어 LO를 암호화하면 RV가 된다. 위치가 다섯 번째 행이라면 첫 번째 행으로 이동하게 된다.
3. 1, 2의 경우를 만족하지 않으면서, 두 글자가 표에서 서로 다른 행, 열에 존재하면, 두 글자가 위치하는 칸의 열이 서로 교환된 위치에 적힌 글자로 암호화된다. 예를 들어 LX를 암호화하면 YV가 된다.
이 과정에 따르면, HELLOWORLD를 Playfair cipher로 암호화한 결과는 EIYVRVVQBRGW가 된다.
현빈이는 어떤 메세지와 키가 주어졌을 때 주어진 메세지를 Playfair cipher로 암호화하려고 한다.
메세지의 길이는 1 이상 1,000 이하이다.
키의 길이는 1 이상 100 이하이다.
첫 번째 줄에 J를 제외한 알파벳 대문자로 이루어진 메세지가 주어진다.
두 번째 줄에 J를 제외한 알파벳 대문자로 이루어진 키가 주어진다.
첫 번째 줄에 Playfair cipher로 암호화된 결과를 출력한다.
HELLOWORLD PLAYFAIRCIPHERKEY
EIYVRVVQBRGW
LEMONSTRAWBERRYAPPLEIUICE WATERMELON
NALNBQEWTANRTZEZTKKOWQWUGW
핵심 설명
단순 빡 구현입니다.
단, 두글자씩 나누는 부분에서 시간초과 신경써주세요
// 두글자씩 나누기 (시간초과 발생)
// for(int i=0; i<mList.size(); i++){
// if(i % 2 == 0){
// if(i == mList.size()-1){ // 끝에 하나만 남은 경우
// mList.add(i+1, 'X');
// }
// else{
// continue;
// }
// }
// else{ // 짝수번째 체크 (i=1, 3, 5, ...)
// char a = mList.get(i-1);
// char b = mList.get(i);
// if(a==b){
// if(a != 'X')
// mList.add(i, 'X');
// else{
// mList.add(i, 'Q');
// }
// }
// }
// }
// 두글자씩 나누기 (시간초과 해결)
for(int i=0; i<mList.size()/2; i++){
char a = mList.get(2*i);
char b = mList.get(2*i + 1);
// 두번째 문자 체크
if(a==b){
if(a != 'X')
mList.add(2*i+1, 'X');
else{
mList.add(2*i+1, 'Q');
}
}
}
if(mList.size() % 2 == 1){ // 끝에 비면 강제추가
mList.add('X');
}
전체코드
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 mStr = br.readLine();
String kStr = br.readLine();
// System.out.println((int)'A'); // 65
// System.out.println((int)'a'); // 97
// ##########################################
// 1. 키 처리 시작
// 문자열부터 앞에 넣기
ArrayList<Character> keyList = new ArrayList<>();
for(int i=0; i<kStr.length(); i++){
char c = kStr.charAt(i);
if(keyList.contains(c) == false){
keyList.add(c);
}
}
// 나머지 문자들 넣기 (J빼고)
for(int i=((int)'A'); i<((int)'Z')+1; i++){
char c = (char)i;
if(keyList.contains(c) == false && c != 'J'){
keyList.add(c);
}
}
// 5개씩 짤라서 다시 저장
char[][] keyMap = new char[5][5];
for(int i=0; i<5; i++){
for(int j=0; j<5; j++) {
keyMap[i][j] = keyList.get( (5*i) + j );
}
}
// 암호화 키 전체 출력
// for(int i=0; i<5; i++){
// for(int j=0; j<5; j++) {
// System.out.print(keyMap[i][j]);
// }
// System.out.println();
// }
// System.out.println("키 출력 완료\n");
// ##########################################
// 2. 메세지 처리 시작
// LL => LX + L?
// XX => XQ
// 한글자 남으면 ?X
// String mStr = br.readLine();
ArrayList<Character> mList = new ArrayList<>();
for(int i=0; i<mStr.length(); i++){
char c = mStr.charAt(i);
mList.add(c);
}
// 두글자씩 나누기 (시간초과 발생)
// for(int i=0; i<mList.size(); i++){
// if(i % 2 == 0){
// if(i == mList.size()-1){ // 끝에 하나만 남은 경우
// mList.add(i+1, 'X');
// }
// else{
// continue;
// }
// }
// else{ // 짝수번째 체크 (i=1, 3, 5, ...)
// char a = mList.get(i-1);
// char b = mList.get(i);
// if(a==b){
// if(a != 'X')
// mList.add(i, 'X');
// else{
// mList.add(i, 'Q');
// }
// }
// }
// }
// 두글자씩 나누기 (시간초과 해결)
for(int i=0; i<mList.size()/2; i++){
char a = mList.get(2*i);
char b = mList.get(2*i + 1);
// 두번째 문자 체크
if(a==b){
if(a != 'X')
mList.add(2*i+1, 'X');
else{
mList.add(2*i+1, 'Q');
}
}
}
if(mList.size() % 2 == 1){ // 끝에 비면 강제추가
mList.add('X');
}
// 암호화 메세지 전체 출력
// for(int i=0; i<mList.size(); i++){
// System.out.print(mList.get(i) );
// if(i % 2 == 1){
// System.out.print(" ");
// }
// }
// System.out.println();
// ##########################################
// 3. 키와 메세지로 마지막 암호화 시작
for(int i=0; i<mList.size()/2; i++){
char c1 = mList.get((2*i));
char c2 = mList.get((2*i) +1);
// 두점 찾기
int c1x = 0, c1y = 0, c2x = 0, c2y = 0;
for(int x=0; x<5; x++){
for(int y=0; y<5; y++) {
if(c1 == keyMap[x][y]){
c1x = x; c1y = y;
}
if(c2 == keyMap[x][y]){
c2x = x; c2y = y;
}
}
}
// 3-1 같은행(x동일)이면 우측1칸이동(y+1),
if(c1x == c2x){
// System.out.println("\n11 : [" + c1x + "," + c1y + "] = " + keyMap[c1x][c1y] + keyMap[c2x][c2y]);
c1y++; c2y++;
if(c1y >= 5){ c1y -= 5;}
if(c2y >= 5){ c2y -= 5;}
mList.set(2*i, keyMap[c1x][c1y]);
mList.set(2*i+1, keyMap[c2x][c2y]);
// System.out.println("12 : [" + c1x + "," + c1y + "] = " + keyMap[c1x][c1y] + keyMap[c2x][c2y]);
}
else if(c1y == c2y){ // 3-2 같은열(y동일)이면 하단1칸이동(x+1)
// System.out.println("21 : [" + c1x + "," + c1y + "] = " + keyMap[c1x][c1y] + keyMap[c2x][c2y]);
c1x++; c2x++;
if(c1x >= 5){ c1x -= 5;}
if(c2x >= 5){ c2x -= 5;}
mList.set(2*i, keyMap[c1x][c1y]);
mList.set(2*i+1, keyMap[c2x][c2y]);
// System.out.println("22 : [" + c1x + "," + c1y + "] = " + keyMap[c1x][c1y] + keyMap[c2x][c2y]);
}
else{ // 3-3 행 열 교환
mList.set(2*i, keyMap[c1x][c2y]);
mList.set(2*i+1, keyMap[c2x][c1y]);
}
}
// 암호화 메세지 전체 최종 출력
// System.out.println();
for(int i=0; i<mList.size(); i++){
// System.out.print(mList.get(i) );
bw.write(String.valueOf(mList.get(i)));
}
// bw.newLine();
// bw.write(String.valueOf(mStr) + "\n");
bw.flush();
bw.close();
}
}
'알고리즘 단련장 > 소프티어' 카테고리의 다른 글
| [소프티어] 통근버스 출발 순서 검증하기 자바 풀이 dp DP (HSAT 4회 정기 코딩 인증평가 기출) (0) | 2024.08.27 |
|---|---|
| [소프티어] 택배 마스터 광우 자바 풀이 dfs 쉽게 접근하기 (2) | 2024.08.26 |
| [소프티어] 함께하는 효도 자바 풀이 dfs 쉽게 설명 쉬운 해설 (0) | 2024.08.25 |
| [소프티어] 나무 섭지 자바 풀이 bfs (시간초과, 런타임에러, 히든테케 해결 완료) (0) | 2024.08.25 |
| [소프티어] 자동차 테스트 자바 풀이 이진탐색 직접구현 함수사용 모두 해보기 (HSAT 7회 정기 코딩 인증평가 기출) (0) | 2024.08.24 |