백준 1213번(팰린드롬 만들기)

♣ 팰린드롬: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 

ex) 스위스, 기러기, 인도인 등

 

 

이미 팰린드롬이 뭔지 알고 있어서 얕봤다가 반례에 큰코 다쳤다. 

 

♣ 팰린드롬의 조건

1. 각각의 문자들이 짝수 개수만큼 있거나

2. 홀수 개수인 문자가 있더라도 딱 한 가지만 있어야 한다. 즉 홀수 개수인 문자가 2개 이상이면 팰린드롬을 만들 수 없다 .

 

♣ 해결 단계

 

[주어진 문자열 확인 단계]

주어진 문자열을 받은 후 각 문자열이 몇 개씩 있는지를 딕셔너리로 만듦. 문자는 key값, 문자의 수는 value값으로 지정함

 

 

 

[팰린드롬이 될 수 없는 경우의 수 제거 단계]

딕셔너리의 value값을 values에 넣는다. odd는 value가 홀수인 값의 수를 의미함. 즉 주어진 input에 개수가 홀수개인 문자가 몇 개 들었나 알아보는 것. odd가 이미 1 이상이면서 현재 다루는 value가 홀수일 때 (1이상인 상태는 이미 홀수 개수인 문자가 하나 있는데 또 홀수 개수는 문자가 나타나서 이 조건을 충족했다는 것이니까) 팰린드롬이 아니게 되므로 "I'm Sorry Hansoo"를 출력한다. 

 

 

[팰린드롬을 만드는 게 가능한 경우, 조건에 따라 팰린드롬 만들기]

먼저 sorted를 사용하여 오름차순으로 알파벳 딕셔너리를 재배열함. 그러면 알파벳을 순서대로 따져서 팰린드롬을 만들 수 있음.

팰린드롬의 앞부분은 front, 팰린드롬의 중간 부분을 middle로 설정한다 .이때 middle은 홀수 개수인 문자가 있을 때만 존재한다. 따라서 items[1]%2 가 0이 아닌 경우에만 middle을 items[0]으로 설정한다. 

그런 뒤 front에 해당 문자를 원래 존재하는 수의 절반만큼만 더해서 문자열을 만든다. 나머지 절반은 뒤로 가야 하기 때문에 남겨둔다 .

문자열을 front+middle+front[::-1]로 하면 팰린드롬을 출력할 수 있다.