본문 바로가기
Algorithm/Baekjoon

1213_팰린드롬 만들기

by 모너아링 2023. 3. 5.

▶실버3

 

문제

 

풀이

생각해야할 것

1. I'm Sorry Hansoo가 출력될 조건 : 문자의 개수가 홀수인 문자가 두 개 이상일 경우

2. 사전 순으로 출력하는 방법

3. 절반 인덱스 지나면 반대로 출력하는 방법

 

먼저 문자의 개수를 세기 위해 배열을 선언하고 입력한 문자의 개수를 센다.

for문으로 A부터 차례대로 탐색하는데,

① 해당 알파벳 개수가 존재하지 않는 경우,

② 알파벳 개수가 홀순데 처음 등장했을 경우,

③ 알파벳 개수가 홀순데 또 등장했을 경우,

④ 알파벳 개수가 짝수인 경우

로 나누어 진행한다.

 

① 해당 알파벳 개수가 존재하지 않는 경우

☞ 다음 과정을 진행하지 않고 건너뛴다.

 

② 알파벳 개수가 홀순데 처음 등장했을 경우

☞ 홀수 개 문자가 등장했다는 것을 불리언 값으로 나타내고, 정답 문자열의 중간에 문자를 하나 넣고, 해당 문자의 개수를 하나 빼 짝수개로 만들어 4번 과정을 진행하도록 한다.

 

③ 알파벳 개수가 홀순데 또 등장했을 경우

☞ I'm Sorry Hansoo 출력하고 종료

 

④ 알파벳 개수가 짝수인 경우

☞ 알파벳 개수의 절반만큼 정답 문자열의 처음과 끝에 해당 문자을 넣는다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <map>
using namespace std;

int cnt[26];
char ans[51];

int main(void) {
	ios::sync_with_stdio(NULL);
	cin.tie(0); cout.tie(0);

	string str;
	cin >> str;

	for (int i = 0; i < str.length(); i++) {
		cnt[str[i] - 'A']++;
	}

	bool isSorry = false;
	int now = 0;
	for (int i = 0; i < 26; i++) {
		//해당 알파벳이 문자열에 존재하지 않을 때
		if (cnt[i] == 0) { continue; }

		//홀수 개인 문자가 처음 등장했을 때
		if (cnt[i] % 2 == 1 && isSorry == false) {
			isSorry = true;
			ans[(str.length() - 1) / 2] = char(i + 'A');
			cnt[i]--;
			if (cnt[i] == 0) { continue; }
		}
		//홀수 개인 문자가 또 등장했을 때
		else if (cnt[i] % 2 == 1 && isSorry == true) {
			cout << "I'm Sorry Hansoo" << endl;
			return 0;
		}
		for (int j = now; j < now + (cnt[i] / 2); j++) {
			ans[j] = char(i + 'A');
			ans[str.length() - 1 - j] = char(i + 'A');
		}
		now += (cnt[i] / 2);
	}
	for (int i = 0; i < str.length(); i++) {
		cout << ans[i];
	}
}

'Algorithm > Baekjoon' 카테고리의 다른 글

1339_단어 수학  (0) 2023.03.08
1080_행렬  (0) 2023.03.07
1965_상자넣기  (0) 2023.03.03
1789_수들의 합  (0) 2023.03.02
1911_흙길 보수하기  (0) 2023.02.28