[백준 20422] 퀼린드롬 (Easy) (C++)

문제 링크: www.acmicpc.net/problem/20422

20422번: 퀼린드롬 (Easy)

1. 주의할 점

- 대칭되는 문자들을 미리 Map에 저장한다

- 하나하나씩 조건들을 만족하면서 풀어나간다

- 문자열의 길이가 홀수일 경우, 가장 중간에 위치한 문자열은 자기자신이 대칭이여야 한다

 

2. 구현

- make_map() 함수를 통해 대칭되는 문자들을 미리 Map에 저장한다

- (문자열의 길이+1)/2만큼 문자들을 비교한다 -> 위의 파란색 조건을 비교하기 위해

- 양끝에서부터 안쪽으로 차례대로 문자들을 비교한다

- 왼쪽에서 고른 문자를 ll 벡터에 넣고, 해당 문자가 알파벳이라면 이에 대응하는 대/소문자 또한 ll벡터에 넣는다. rr 벡터에는 오른쪽에서 고른 문자를 ll와 같은 방식으로 넣는다

- ll에 넣은 문자중 1개를 고른 후, 해당 문자에 대칭되는 문자가 있다면 rr벡터에 있는지 확인한다. 있으면 ll에서 고른 문자를 sl의 끝에, rr에서 고른 문자를 sr의 앞에 추가한다. 단, 고른 문자의 위치가 전체 문자열의 중간이면 sl에만 추가한다

- 퀼린드롬이면 sl+sr을, 아니라면 -1을 출력한다

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <vector>
using namespace std;
map<char, char> m;

void make_map() {
	m['A'] = 'A';
	m['E'] = '3';
	m['3'] = 'E';
	m['H'] = 'H';
	m['I'] = 'I';
	m['M'] = 'M';
	m['O'] = 'O';
	m['S'] = '2';
	m['2'] = 'S';
	m['T'] = 'T';
	m['U'] = 'U';
	m['V'] = 'V';
	m['W'] = 'W';
	m['X'] = 'X';
	m['Y'] = 'Y';
	m['Z'] = '5';
	m['5'] = 'Z';
	m['b'] = 'd';
	m['d'] = 'b';
	m['i'] = 'i';
	m['l'] = 'l';
	m['m'] = 'm';
	m['n'] = 'n';
	m['o'] = 'o';
	m['p'] = 'q';
	m['q'] = 'p';
	m['r'] = '7';
	m['7'] = 'r';
	m['u'] = 'u';
	m['v'] = 'v';
	m['w'] = 'w';
	m['x'] = 'x';
	m['0'] = '0';
	m['1'] = '1';
	m['8'] = '8';
}

bool isSmallAlpha(char c) {
	if('a' <= c && c <= 'z') return true;
	return false;
}

bool isBigAlpha(char c) {
	if ('A' <= c && c <= 'Z') return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string str, sr = "", sl = "";
	cin >> str;
	make_map();
	bool avail = true;
	int len = str.size();
	for (int i = 0; i < (len+1) / 2; i++) {
		char l = str[i];
		char r = str[len - 1 - i];
		vector<char> ll, rr;
		ll.push_back(l);
		if (isSmallAlpha(l))
			ll.push_back(l - 'a' + 'A');
		else if (isBigAlpha(l))
			ll.push_back(l - 'A' + 'a');

		rr.push_back(r);
		if (isSmallAlpha(r))
			rr.push_back(r - 'a' + 'A');
		else if (isBigAlpha(r))
			rr.push_back(r - 'A' + 'a');
		bool matched = false;
		for (int j = 0; j < ll.size(); j++) {
			char c = ll[j];
			if (m.find(c) != m.end()) {
				char cc = m[c];
				for (int k = 0; k < rr.size(); k++) {
					if (cc == rr[k]) {
						matched = true;
						sl += c;
						if (i != len - 1 - i)
							sr = cc + sr;
						break;
					}
				}
			}
			if (matched) break;
		}
		if (!matched) {
			avail = false;
			break;
		}
	}
	avail ? cout << sl + sr : cout << -1;
	return 0;
}