[소프티어] 플레이페어 암호 / C++ 해설

더 많은 문제풀이는 아래 Github 주소에서 확인하실 수 있습니다.

https://github.com/Dongha-k/softeer-code

GitHub - Dongha-k/softeer-code: softeer 문제 풀이입니다.

문제 출처: https://softeer.ai/practice/info.do?idx=1&eid=804 

Softeer

 

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef pair<int, int> P;
P position[26];
bool used[26] = {false, };
char table[5][5] = {0, };
int main(int argc, char** argv) {
	string message, key;
	cin >> message >> key;
	
	// J -> I
	for(auto& m : message) if(m == 'J') m = 'I';
	for(auto& k : key) if(k == 'J') key = 'I';
	
	int idx = 0;
	for(char k : key){
		if(used[k-'A']) continue;
		used[k-'A'] = true;
		table[idx / 5][idx % 5] = k;
		idx ++;
	}
	
	used['J' - 'A'] = true;

	for(int i = 0 ; i < 26 ; i ++){
		if(used[i]) continue;
		used[i] = true;
		table[idx / 5][idx % 5] = i + 'A';
		idx ++;
	}
	

	for(int i = 0 ; i < 5 ; i ++){
		for(int j = 0 ; j < 5 ; j ++){
			position[table[i][j] - 'A'] = {i, j};
		}
	}

	string encoded_msg = "";

	for(int i = 0 ; i < message.size() ; i ++){
		if(encoded_msg.size() % 2 == 1 and encoded_msg.back() == message[i]){	
			if(encoded_msg.back() == 'X') encoded_msg += 'Q';
			else encoded_msg += 'X';
		}
		encoded_msg += message[i];
	}

	
	if(encoded_msg.size() % 2 == 1) encoded_msg += 'X';
	
	vector<pair<char, char>> v;
	
	for(int i = 0 ; i < encoded_msg.size() ; i += 2){
		v.push_back({encoded_msg[i], encoded_msg[i + 1]});
	}



	string result = "";
	for(auto x : v){
		char a = x.first;
		char b = x.second;
		int a_x = position[a-'A'].first;
		int a_y = position[a-'A'].second;
		int b_x = position[b-'A'].first;
		int b_y = position[b-'A'].second;

		if(a_x == b_x){
			result += table[a_x][(a_y + 1) % 5];
			result += table[b_x][(b_y + 1) % 5];
		}
		else if(a_y == b_y){
			result += table[(a_x + 1) % 5][a_y];
			result += table[(b_x + 1) % 5][b_y];
		}
		else{
			result += table[a_x][b_y];
			result += table[b_x][a_y];
			
		}
	}
	cout << result;

	


	return 0;
}

 

구현쪽에 가까운 재밌는 문제이다.

 

풀이

 

 

1. 5x5 테이블 만들기

keyword 문자열을 처음부터 끝까지 for문으로 돌면서 used라는 배열로 사용안한 알파벳의 경우 차례대로 넣어주었다. 왼쪽 상단부터 오른쪽 하단까지 내려갈 때 table[idx / 5][idx % 5]로 접근하면 차근차근 순서대로 쌓을 수 있다. 그리고 나머지 사용 안한 알파벳들을 순서대로 쌓아주었다.

 

2. 알파벳으로 좌표를 조회할 수 있는 position 배열 만들기

알파벳의 위치를 역추적해야하기 때문에 position 배열에 담아주었다.

ex) 'Z'라는 문자가 4, 4에 있으면 position['Z'-'A']의 값은 {4, 4}이다.

 

3. 짝 만들기

짝을 만들기전에 encoded_msg 문자열에 문제조건에 부합하는 알파벳 짝이 없는 문자열을 만들었다.

message를 순서대로 하나씩 넣기 전에 encoded_msg의 크기가 홀수이면 가장 마지막에 알파벳이랑 message[i]가 동일할 경우 마지막 알파벳이 X이면 Q를 넣고 message[i]인 X를 넣는다. 마지막 알파벳이 X가 아니면 X를 넣고 message[i]인 X가 아닌 알파벳을 넣는다.

반복문을 빠져나오고 encoded_msg의 크기가 홀수이면 'X'를 가장 마지막에 추가해준다.

그 이후 Pair<int, int>를 데이터로 가지는 짝 배열이라고도 할 수 있는 vector에 차례대로 두개씩 넣는다.

 

4. 짝 배열을 순서대로 조회해서 결과를 출력한다.

 

테이블과 position(2번에서 만든거) 배열을 이용하면 현재 무슨 알파벳 짝이고 어느 위치에 알파벳이 존재하는지 알기 때문에 결과는 쉽게 구해진다.

 

 

 

주의할 점

 

문제가 굉장히 긴편이고 구현 문제의 특성상 조건이 많아 빼먹기 쉬운데 조심하면 좋을 것 같다.