1213번: 팰린드롬 만들기
첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.
www.acmicpc.net
뇌를 자극하는 C++ STL을 공부하면서 배운 내용을 사용해볼 수 있어서 재밌게 푼 문제였다.
처음엔 next_permutation() 함수를 사용해서 구현해보았지만 알파벳 개수가 50개까지 있어서 시간초과가 발생했다.
따라서 다른 방식으로 구현하기로 하였고, 그 방법은 다음과 같다.
1. 입력받은 문자열을 오름차순으로 정렬한다.
2. 문자열의 첫 번째 원소를 가리키는 반복자를 만든 다음 count()함수를 통해 반복자가 가리키는 실제 값이 몇개 존재하는지 확인한다.
IF : 만약 홀수개라면 홀수갯수를 1 증가시킨 다음 (이 때 홀수갯수가 2개 이상이라면 팰린드롬을 만들 수 없기 때문에 " I'm Sorry Hansoo " 출력 후 프로그램을 종료한다.) 값을 char 변수에 저장하고 erase() 멤버함수를 사용해 원소 하나를 삭제한다.
3. 문자 개수의 절반을 stack에 담고 문자열에서 삭제한다. 그리고 반복자가 다음 알파벳을 가리키도록 이동시킨다.
4. 모든 원소에 대해 작업을 마쳤다면 char변수에 저장한 홀수개 알파벳을 문자열 뒤에 붙이고 (없다면 건너뜀)
스택에 저장한 원소를 늦게 들어온 순서대로 문자열 뒤에 붙여준다.
5. 완성!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
int main(void)
{
string str;
cin >> str;
sort(str.begin(), str.end());
string::iterator iter = str.begin();
stack<char> alpha;
char oddChar;
while (cnt < strLen)
{
int c = count(str.begin(), str.end(), *iter);
if (c % 2 != 0)
{
oddCnt++; // 홀수개로 존재하는 알파벳 개수카운팅
if (oddCnt == 2) // 홀수개가 두개 이상이면 안됨
{
cout << "I'm Sorry Hansoo" << endl;
return 0;
}
oddChar = *iter;
iter = str.erase(iter);
}
int n = c / 2;
while (n--)
{
alpha.push(*iter);
iter = str.erase(iter);
}
cnt += c;
iter += c / 2;
}
if(oddCnt == 1) str.push_back(oddChar);
{
str.push_back(alpha.top());
alpha.pop();
}
cout << str << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 25day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2858번: 기숙사 바닥 (0) | 2020.05.05 |
|---|---|
| 백준 1405번: 미친 로봇 (0) | 2020.05.03 |
| 백준 2981번: 검문 (0) | 2020.04.30 |
| 백준 1062번: 가르침 (0) | 2020.04.29 |
| 백준 6679번: 싱기한 네자리 숫자 (0) | 2020.04.28 |