[백준/C++] 26266 비즈네르 암호 해독

https://www.acmicpc.net/problem/26266

26266번: 비즈네르 암호 해독

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> makeNumber(string s) {
	vector <int> result;
	for (int i = 1; i <= s.length(); i++)
		if (s.length() % i == 0) result.push_back(i);
	return result;
}

int main()
{
	string p, result;
	int keyLength=1;
	cin >> p >> result;

	vector<int> pv(p.length());
	vector<int> rv(result.length());
	for (int i = 0; i < p.length(); i++) pv[i] = p[i] - 'A' + 1;
	for (int i = 0; i < result.length(); i++) rv[i] = result[i] - 'A' + 1;

	vector<int> keyV(p.length());
	vector<int> v = makeNumber(p);
	for (int i = 0; i < p.length(); i++) {
		int c = (rv[i] - pv[i] > 0) ? rv[i] - pv[i] : rv[i] - pv[i] + 26;
		keyV[i] = c;
	}
	
	for (int i = 0, j; i < v.size(); i++) {
		int c = v[i];
		for (j = 0; j < keyV.size(); j++) {
			if (c + j >= keyV.size()) continue;
			if (keyV[j] != keyV[c + j]) break;
		}
		if (j == keyV.size()) {
			keyLength = c;
			break;
		}
	}

	for (int i = 0; i < keyLength; i++) cout << (char)(keyV[i] + 'A' - 1);
	return 0;
}

 

코드 설명

평문과 비즈네르 암호문을 받을 변수를 각각 string형 p, result로 선언 후 입력받는다. 이후 vector들을 만들어주는데, pv는 평문의 알파벳들을 숫자로 대응시킨 결과, rv는 비즈네르 암호문의 알파벳을 숫자로 대응시킨 결과이다. 반복문으로 pv, rv에 값을 넣어준다.
 
키 수열을 저장할 벡터를 선언하고 키의 길이가 될 수 있는 값들을 makeNumber 함수를 이용해 구한다. 키를 단순 반복해 평문과 동일한 길이를 만들 수 있다고 하였으므로 키의 길이가 될 수 있는 값들은 평문 길이의 약수이다.
 
평문 수열[i]+ 키 수열[i] = 비즈네르 암호문 수열[i]이므로  키 수열을 구하기 위해 반복문을 이용해서 비즈네르 암호문 수열[i]- 평문 수열[i]의 값을 구한다. 해당 값이 음수가 되지 않도록 삼항 연산자를 통해 0 이하의 값일 경우 26을 값에 더해주고 이 값을 키 수열 벡터에 넣는다.
 
평문 길이의 약수 개수에 대해 반복문을 수행하면서 키의 길이가 가장 짧은 경우를 구한다. 내부 반복문에서는 약수만큼의 간격을 둔 두 숫자가 같은지 검사하는데,이때 두 숫자가 다를 경우 키가 아니다. 내부 반복문을 끝까지 돌았다면 약수만큼의 간격을 둔 두 숫자가 모두 같다는 뜻으로 이 약수가 키의 길이가 된다.
 
마지막으로 키의 길이만큼 반복문을 돌면서 숫자를 알파벳으로 변환한 값을 출력해준다.
 

느낀 점

문제를 읽고 바로 머릿속으로 흐름을 세워 막힘없이 풀었던 문제다. 코드의 길이가 약간 긴 편이라 아쉽긴 했지만 한 번에 성공해서 기분이 좋았다!