2024 - 04 - 30 C++ 코딩테스트 10주완성 D+11

백준 1213 - 팰린드롬 문제

 

입력받은 문자열을 팰린드롬 형식으로 변환시키는 문제이다.

 

팰린드롬 형식으로 변환시킬 수 없을 때에는 I'm Sorry HanSoo 라고 출력한다.

 

먼저 입력받은 문자열의 알파벳의 개수를 정수형 배열을 이용하여 저장한다.

 

예) AAABBB , AAABBCCC 등은 아무리 조합하여도 팰린드롬 형식이 나오지 않는다.

 

팰린드롬이 성립하지 않는 조건은 홀수인 알파벳이 2개 이상일 경우이기 때문에

 

홀수인 알파벳이 나올때마다 정수형 변수 flag를 증감해주어 2개 이상일 경우 I'm Sorry Hansoo 를 출력하여준다.

 

하지만 1개인 경우에는 중간에 해당 알파벳을 넣어주면 팰린드롬이 성립하므로 홀수인 알파벳이 있을 경우

 

문자 변수 mid 에 해당 알파벳을 저장을 시켜준다.

 

그리고 아닐 경우에는 똑같은 문자열을 만들어서 반대로 뒤집어서 다시 더해주면 팰린드롬이 완성되기때문에

 

왼쪽 즉 절반의 문자열을 먼저 완성시킨 다음에 그 문자열을 뒤집어서 더해주면 된다.

 

(각 알파벳의 개수) / 2 만큼 반복하여 절반의 문자열 ret 안에 해당 알파벳을 추가시켜준다.

 

반복문이 끝난 후 이제 쓰지 않는 문자열 s를 이용하여 ret 을 초기화 및 대입하고

 

String 라이브러리에서 지원하는 reverse 메서드를 이용하여 앞뒤를 바꿔준다.

 

만약 홀수인 알파벳이 있을 경우 중간에 ret의 마지막 지점에 홀수인 알파벳을 저장해둔 mid를 추가한다.

 

그 후 문자열 ret에 s를 추가시켜주고 출력시켜주면 팰린드롬 완성!

 

#include<bits/stdc++.h> 
using namespace std;
string s, ret;
int cnt[100], flag , midCnt;
char mid;
int main() {
	
	cin >> s;

	for (int i = 0; i < s.length(); i++)
	{		
		cnt[s[i]-65]++;
	}
	
	for (int j = 0; j < 26; j++)
	{
		if (cnt[j] != 0)
		{
			if (cnt[j] % 2 == 1)
			{
				mid = (char)(j + 65);
				flag++;
				if (flag >= 2)
				{
					cout << "I'm Sorry Hansoo";
					return 0;
				}
			}
			// 조건인 홀수와 짝수가 각각 하나인 경우에는 성립하지 않음.
			//else if (cnt[j] >= 2 && cnt[j] % 2 == 0)	//그냥 else 라고 해도 되지만 명시적으로 표현
			//{
			//	for (int a = 0; a < cnt[j] / 2; a++)
			//		ret += (char)(j + 65);
			//}
			
			// 그냥 짝수인 조건을 제외하고 
			// 홀수도 문자열에 추가 시킨 다음 중간에다가 홀수알파벳을 넣으면 됌
			for (int a = 0; a < cnt[j] / 2; a++)
				ret += (char)(j + 65);
		}
	}	
	s = ret;
	reverse(s.begin(), s.end());

	if (flag > 0)
	{		
			ret += mid;
	}
	ret += s;

	cout << ret;
	return 0;
}

 

강의내용에서 나온 실습코드

 

#include<bits/stdc++.h> 
using namespace std;
string s, ret;
int cnt[200], flag;
char mid;
int main() {

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";
}

 

코드가 동작하는 알고리즘은 비슷하나, 코드 내용수가 많이 줄어 있는 모습이다.

 

 

<차이점>

 

1.알파벳의 개수가 없는 조건문을 cnt[i] != 0 이 아닌 cnt[i] 으로 표현하여 1 이상일 경우에만 코드가 동작하게 만들었다.

 

2.홀수일 경우 해당 알파벳 배열 카운트를 -- 해주었다.

 

3.마지막 반복문에서 ret 문자열을 절반으로 추가하고 뒤집어서 추가하는 방식이 아닌

 

처음부터 끝까지 전부 추가를 시켜준뒤 홀수인 알파벳이 있을 경우 그 중간에 홀수 알파벳을 추가시켜주는 방식의 알고리

 

즘이다.