반응형

문제 출처 :


https://www.acmicpc.net/problem/1213



알고리즘 분석 :


문제 해결에 필요한 사항

1. 팰린드롬


이 문제에서 이름을 팰린드롬으로 바꾸어야 하는데 방법은 다음과 같다.

1. 홀수 개수의 알파벳이 최대 1개여야 한다.

예를들어 AABBBCC는 되지만, AABCDD는 홀수 개수 알파벳이 B,C로 두개여서 안된다.


2. 홀수 개수가 판별이 났다면 알파벳 사전 순('A'~'Z')으로 앞, 뒤로 하나씩 붙여준다.


3. 이때 홀수 개수는 앞,뒤로 하나씩 붙이다 결국 하나가 남게 되는데, 그것을 중간에 마지막으로 붙여주고 끝을 낸다.



소스 코드를 두개를 올리는데 하나는 문제의 AC 코드이고 하나는 TLE코드이지만, 

팰린드롬을 dfs로 처음에 구상한 내용을 올려두려 한다.







소스 코드 : 


(AC 코드)

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
 
using namespace std;
 
int alpha[100];
 
int main()
{
    string str;
    cin >> str;
 
    // 알파벳 개수 카운트
    for (int i = 0; i < str.size(); i++)
    {
        char ch = str[i];
        alpha[(int)ch]++;
    }
 
    // 알파벳에 홀수가 2번이상 나오면 팰린드롬 안됨
    int holsu = 0;
    for (int i = 65; i <= 90; i++)
        if (alpha[i] % == 1)
            holsu++;
 
    if (holsu >= 2)
    {
        printf("I'm Sorry Hansoo");
        return 0;
    }
 
    // 홀수 알파벳 가져온다
    string hol;
    for (int i = 65; i <= 90; i++)
        if (alpha[i] % == 1)
            hol = (char)i;
 
    string ans;
 
    // 2 이상인 알파벳에 대해 앞, 뒤로 붙인다.
    for (int i = 90; i >= 65; i--)
        while (alpha[i] >= 2)
        {
            ans.insert(ans.begin(), (char)i);
            ans.push_back((char)i);
            alpha[i] -= 2;
        }
 
    // 홀수가 존재할 경우 홀수 알파벳을 중앙에 붙인다.
    if (hol.size() == 1)
        while (alpha[(int)hol[0]]--)
            ans.insert(ans.begin() + ans.size() / 2, hol[0]);
 
    cout << ans;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





(TLE 코드)


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
#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
bool visit[100];
void dfs(string tmp, string str, int n)
{
    string pallindrome = tmp;
    reverse(pallindrome.begin(), pallindrome.end());
 
    if (tmp.size() == str.size() && tmp.compare(pallindrome) == 0)
    {
        cout << tmp << endl;
        exit(0);
    }
    for (int i = 0; i < str.size(); i++)
    {
        if (visit[i])
            continue;
        visit[i] = true;
        dfs(tmp + str[i], str, i + 1);
        visit[i] = false;
    }
}
int main()
{
    string str;
    cin >> str;
 
    dfs("", str, 0);
    printf("I'm Sorry Hansoo");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1377번] 버블 소트  (0) 2017.04.27
[1915번] 가장 큰 정사각형  (0) 2017.04.26
[1015번] 수열 정렬  (2) 2017.04.25
[2038번] 골롱 수열  (2) 2017.04.25
[2293번] 동전 1  (0) 2017.04.25