Softeer - [HSAT 3회 정기 코딩 인증평가 기출] 플레이페어 암호
답
##step 1
planetext = str(input());
key = str(input());
tmp = [];
tmp2 = list(range(5));
password_key = [];
for i in key:
if i not in tmp:
tmp.append(i);
alphabet = list("ABCDEFGHIKLMNOPQRSTUVWXYZ");
for i in alphabet:
if i not in tmp:
tmp.append(i);
if len(tmp) == 25:
break
for i in range(0,25,5):
for j in range(5):
tmp2[j] = tmp[i+j]
password_key.append(tmp2.copy())
##step 2
planetext_split = [];
planetext_list = list(planetext);
k = 0
while k < len(planetext_list):
tmp = planetext_list[k:k+2];
if len(tmp) < 2:
planetext_list.append("X");
elif tmp[0] == tmp[1]:
if tmp[0] == 'X' and tmp[1] == 'X':
planetext_list.insert(k+1, 'Q');
else:
planetext_list.insert(k+1, 'X');
k = k + 2;
##step 3
def encryption(x, y):
a, b = 0, 0;
for i in range(5):
for j in range(5):
if password_key[i][j] == x:
# x_1: x의 행, x_2: x의 열
x_1, x_2 = i, j;
a = 1;
if password_key[i][j] == y:
# y_1: y의 행, y_2: y의 열
y_1, y_2 = i, j;
b = 1;
if a == 1 and b == 1:
break
if a == 1 and b == 1:
break
if x_1 == y_1: # x와 y의 행이 같을 경우
return [1, x_1, x_2, y_2];
elif x_2 == y_2: # x와 y의 열이 같을 경우
return [2, x_2, x_1, y_1];
else: # x와 y의 행, 열이 다른 경우
return [3, x_1, x_2, y_1, y_2];
l = 0
answer = ""
while l < len(planetext_list):
result = encryption(planetext_list[l], planetext_list[l+1]);
if result[0] == 1: # x와 y의 행이 같을 경우 -> 열을 변경
answer = answer + str(password_key[result[1]][(result[2]+1)%5])
answer = answer + str(password_key[result[1]][(result[3]+1)%5]);
elif result[0] == 2: # x와 y의 열이 같을 경우 -> 행을 변경
answer = answer + str(password_key[(result[2]+1)%5][result[1]]);
answer = answer + str(password_key[(result[3]+1)%5][result[1]]);
elif result[0] == 3: # x와 y의 행, 열이 다른 경우 -> 행 유지, 열을 변경
answer = answer + str(password_key[result[1]][result[4]]);
answer = answer + str(password_key[result[3]][result[2]]);
l = l + 2;
print(answer)
풀이
Step 1
일단 먼저 5x5 표를 만들어야 한다. 이를 위해서는 2차원 배열을 만드려고 했는데, 이 과정에서 2가지 방식을 사용해보았다
1) numpy 사용
import numpy as np;
planetext = str(input());
key = str(input());
tmp = [];
password_key = [];
for i in key:
if i not in tmp:
tmp.append(i);
alphabet = list("ABCDEFGHIKLMNOPQRSTUVWXYZ");
for i in alphabet:
if i not in tmp:
tmp.append(i);
if len(tmp) == 25:
break
arr = np.array(tmp);
password_key = arr.reshape(5,5);코드가 간결하고 편하다. numpy의 array와 reshape를 통해 편하게 5x5 행렬을 구현할 수 있다. 근데 개인적으로 이건 python의 다른 라이브러리를 불러온거라, 라이브러리 없이 기본 함수들만으로 구현하는 방식도 사용해보고 싶었다.
2) numpy 사용 x
planetext = str(input());
key = str(input());
tmp = [];
tmp2 = list(range(5));
password_key = [];
for i in key:
if i not in tmp:
tmp.append(i);
alphabet = list("ABCDEFGHIKLMNOPQRSTUVWXYZ");
for i in alphabet:
if i not in tmp:
tmp.append(i);
if len(tmp) == 25:
break
for i in range(0,25,5):
for j in range(5):
tmp2[j] = tmp[i+j]
password_key.append(tmp2.copy())
여기서는 한 가지 문제가 있어 구글링을 통해 해결하였다.
for i in range(0,25,5):
for j in range(5):
tmp2[j] = tmp[i+j]
print(tmp2) #디버깅용
password_key.append(tmp2)
print(password_key) #디버깅용5x5 행렬을 만들기 위해 요소 5개씩 작은 리스트로 만들고, 이를 다시 큰 리스트에 넣어 만들기 위해 위와 같은 반복문을 구상하였다.
그런데 결과가
디버깅용 print(tmp2)로 작은 리스트들은 정상적으로 생성된 것을 확인했으나, 큰 리스트는 맨 마지막 작은 리스트로만 이루어진 5x5 행렬이 나왔다. 원인을 모르겠어 검색을 해보니, 참조 때문인 것을 알게 되었다.
python에서 리스트는 참조 타입이기 때문에 password_key.append(tmp2)가 호출 되면 tmp2의 값이 추가되는 것이 아니라, tmp2의 참조가 추가된다. 때문에 나중에 tmp2의 값이 바뀌면 참조에 의해 password_key에 이미 추가된 내용도 영향을 받는다. 그래서 맨 마지막으로 작은 리스트 tmp2 = ['U', 'V', 'W', 'X', 'Z']가 되었을 때 큰 리스트 전체가 참조에 의해 사진과 같은 형태가 된 것이다. 그래서 참조가 아닌 값을 복사하기 위해 copy()를 사용하였다.
for i in range(0,25,5):
for j in range(5):
tmp2[j] = tmp[i+j]
password_key.append(tmp2.copy())Step 2
다음으로 암호화하려는 메세지를 두 글자씩 나누고, 같은 두 글자로 이루어진 쌍과 맨 마지막 1글자에 대한 처리를 해줘야 한다.
planetext_split = [];
planetext_list = list(planetext);
k = 0
while k < len(planetext_list):
tmp = planetext_list[k:k+2];
if len(tmp) < 2:
planetext_list.append("X");
elif tmp[0] == tmp[1]:
if tmp[0] == 'X' and tmp[1] == 'X':
planetext_list.insert(k+1, 'Q');
else:
planetext_list.insert(k+1, 'X');
k = k + 2;체점 중 시간 초과가 한번 발생했는데, 아마 이 부분에서 발생했던 것 같다. 첫 제출에서는 elif 조건문이 처리될 때 마다 k = 0으로 초기화하여 처음부터 다시 검사하도록 코드를 구상했다. 그러다보니 입력값 planetext가 길어지면 반복문이 너무 많이 실행되었고, 여기서 시간 초과가 발생했다고 판단했다. 코드를 조금 더 분석하니 굳이 k = 0으로 초기화하여 재검사하지 않아도 문제가 발생하지 않는다는걸 알아서 수정하였다.
Step 3
def encryption(x, y):
a, b = 0, 0;
for i in range(5):
for j in range(5):
if password_key[i][j] == x:
# x_1: x의 행, x_2: x의 열
x_1, x_2 = i, j;
a = 1;
if password_key[i][j] == y:
# y_1: y의 행, y_2: y의 열
y_1, y_2 = i, j;
b = 1;
if a == 1 and b == 1:
break
if a == 1 and b == 1:
break
if x_1 == y_1: # x와 y의 행이 같을 경우
return [1, x_1, x_2, y_2];
elif x_2 == y_2: # x와 y의 열이 같을 경우
return [2, x_2, x_1, y_1];
else: # x와 y의 행, 열이 다른 경우
return [3, x_1, x_2, y_1, y_2];
l = 0
answer = ""
while l < len(planetext_list):
result = encryption(planetext_list[l], planetext_list[l+1]);
if result[0] == 1: # x와 y의 행이 같을 경우 -> 열을 변경
answer = answer + str(password_key[result[1]][(result[2]+1)%5])
answer = answer + str(password_key[result[1]][(result[3]+1)%5]);
elif result[0] == 2: # x와 y의 열이 같을 경우 -> 행을 변경
answer = answer + str(password_key[(result[2]+1)%5][result[1]]);
answer = answer + str(password_key[(result[3]+1)%5][result[1]]);
elif result[0] == 3: # x와 y의 행, 열이 다른 경우 -> 행 유지, 열을 변경
answer = answer + str(password_key[result[1]][result[4]]);
answer = answer + str(password_key[result[3]][result[2]]);
l = l + 2;
print(answer)
이제 암호화를 진행하는 단계인데, 5x5 행렬에서 2개씩 나눈 문자들의 위치를 찾고 행, 열 값을 구해야 한다. 이를 encryption 함수로 구현했는데, return 값을 배열 형태로 해서 3가지 유형 중 어떤 유형인지와 그 유형일 때 필요한 값(행, 열)을 담아서 반환하였다.
이후 아래 while 반복문을 통해 유형 별로 암호화를 처리하였고, answer이라는 문자열에 순서대로 암호화된 문자들을 순서대로 넣어 최종 답안을 문자열 형태로 출력할 수 있도록 만들었다.
풀이에 있어 시간이 조금 걸렸지만, 구글링 없이 로직을 직접 짜서 풀었다는 점에서 만족하였고 참조라는 개념에 대해 알게 되었다.
cf) 언어별 참조
1. Python
Python에서 모든 객체는 기본적으로 참조로 다뤄짐. 변수에 객체를 할당하면, 그 객체의 참조가 변수에 저장되고, 그 객체를 다른 변수나 자료구조에 할당하면 그 객체를 가리키는 참조만 복사됨. 값이 아닌 참조가 복사되는 것.
2. C/C++
기본적으로 값 복사가 이루어지지만, 포인터를 사용해 참조와 비슷하게 동작할 수 있음.
3. Java
Java에서 변수에 객체를 할당할 때, 객체의 참조가 전달됨. 즉, 변수에 할당된 객체를 다른 변수에 대입하면 참조가 복사되는 방식이지만 모든 변수가 그런 것은 아님.
기본형 타입 (primitive types): 값을 복사 (예: int, float, char).
참조형 타입 (reference types): 객체에 대한 참조가 복사됨.
4. JavaScript
JavaScript에서 기본형 데이터(number, string 등)는 값 복사가 이루어지고, 객체(배열, 객체 등)는 참조로 처리됨.
