[BOJ-1213] C++ 팰린드롬 만들기 / 실버3

1213번: 팰린드롬 만들기

 

솔루션

초기 풀이는 조합으로 AABB일때 모든 경우의 수를 세고 난다음에 푸는 방식으로 재귀로 풀었는데 시간초과가 나서 다른 방법을 찾았다.

#include <iostream>
#include <map>
#include <algorithm>
#include <climits>
#include <string>
using namespace std;

void isPalindrome(string str)
{
    string temp = str;
    reverse(temp.begin(), temp.end());
    if (str == temp)
    {
        cout << str << "\n";
        exit(0);
    }
}

void solve(string str,int n, int r, int depth)
{
    if (r == depth)
    {
        isPalindrome(str);
        return;
    }

    for (int i = depth; i <= n; i++)
    {
        swap(str[i], str[depth]);
        solve(str, n, r, depth + 1);
        swap(str[i], str[depth]);
    }
}

int main() {
    string str;
    cin >> str;
    solve(str, str.size(), str.size(), 0);
    cout << "I'm Sorry Hansoo" << "\n";
    return 0;
}

 

초기풀이 이게 되게 할수는없을까...? 아시는분은 댓글 남겨주세요 

 

개선풀이

팰린드롬을 만들려면 홀수개의 알파벳이 2개 이상 존재하면 안된다.

ex) AAAB -> I'm sorry Hansoo

따라서, 알파벳 갯수를 확인하고 홀수의 알파벳이 몇개인지 체크 후 flag로 기록.

if (cnt[i] & 1) {  // 홀수인 경우
    mid = char(i); // 중앙에 배치할 문자
    flag++;
    cnt[i]--;      // 사용 후 개수를 짝수로 만듦
}
if (flag == 2) break; // 홀수 문자가 2개 이상이면 중단

 

팰린드롬 생성

* 대칭 구조를 가짐. (따라서, 알파벳을 사전순으로 배치하면서 반씩 나누어 문자열 앞뒤에 삽입)

for (int j = 0; j < cnt[i]; j += 2) {
    ret = char(i) + ret; // 앞에 추가
    ret += char(i);      // 뒤에 추가
}

만약 중앙에 배치할 문자가 있으면, 생성한 팰린드롬의 가운데에 삽입.

if (mid) ret.insert(ret.begin() + ret.size() / 2, mid);

 

결론 핵심

 

• 홀수 개의 알파벳이 2개 이상 존재하면 팰린드롬을 만들 수 없다.
• 사전순으로 가장 앞서는 팰린드롬을 만들기 위해 큰 알파벳부터 처리한다.

이 두 가지를 확인하고 문제를 해결하면 된다.

 

#include <iostream>
#include <map>
#include <algorithm>
#include <climits>
#include <string>
using namespace std;

string s, ret;
int cnt[200], flag;
char mid;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> s;
	for (char a : s)cnt[a]++;
	for (int i = 'Z'; i >= 'A'; i--) {
		if (cnt[i]) {
			if (cnt[i] & 1) {
				mid = char(i); flag++;
				cnt[i]--;
			}
			if (flag == 2)break;
			for (int j = 0; j < cnt[i]; j += 2) {
				ret = char(i) + ret;
				ret += char(i);
			}
		}
	}
	if (mid)ret.insert(ret.begin() + ret.size() / 2, mid);
	if (flag == 2)cout << "I'm Sorry Hansoo\n";
	else cout << ret << "\n";
	return 0;
}