백준# 1213 - 팰린드롬 만들기

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

1213번: 팰린드롬 만들기

정렬로 분류된 팰린드롬 만들기 입니다.

 

* 팰린드롬이란 앞에서 읽어도, 뒤로 읽어도 똑같은 문자열을 말합니다.

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1213
{
    class Program
    {
        static void Main(string[] args)
        {
            string name = Console.ReadLine();
            var charDict = new Dictionary<string, int>();
 
            foreach(var subString in name.Select(x => x + ""))
            {
                int count;
                if (charDict.TryGetValue(subString, out count))
                    charDict[subString] = count + 1;
                else
                    charDict[subString] = 1;
            }
 
            //입력 딕셔너리에서 갯수가 홀수개인 것을 문자에 대해 정렬.
            var oddDict = charDict.Where(x => x.Value % 2 != 0)
                .OrderBy(x => x.Key).ToDictionary(x => x.Key, x => x.Value);
            
            //홀수개인 알파벳이 하나보다 많다면 만들 수 없음.
            if(oddDict.Count > 1)
            {
                Console.Write("I'm Sorry Hansoo");
                return;
            }
 
            //짝수개인 알파벳 딕셔너리를 키값에 대해 정렬해 가지고 있음.
            var evenDict = charDict.Where(x => x.Value % 2 == 0)
                .ToDictionary(x => x.Key, x => x.Value);
 
            //홀수개인 알파벳이 하나일 때.
            if (oddDict.Count == 1)
                evenDict.Add(oddDict.First().Key, oddDict.First().Value - 1);
 
            //짝수 알파벳 딕셔너리 키값에 대해 정렬.
            evenDict = evenDict.OrderBy(x => x.Key)
                .ToDictionary(x => x.Key, x => x.Value);
 
            foreach(var kvp in evenDict)
            {
                for (int i = 0; i < kvp.Value / 2; i++)
                    Console.Write(kvp.Key);
            }
            if (oddDict.Count == 1)
                Console.Write(oddDict.First().Key);
 
            foreach (var kvp in evenDict.Reverse())
            {
                for (int i = 0; i < kvp.Value / 2; i++)
                    Console.Write(kvp.Key);
            }
        }
    }
}
 

입력받은 문자열을 각각 알파벳 하나씩 떼어서 부분문자열을 만들고 그것의

갯수를 세어 딕셔너리에 넣었습니다.

 

핵심은 등장하는 횟수가 홀수인 문자의 갯수가 되겠습니다.

 

ex) AAABBB 이렇게 있을 경우 갯수가 홀수인 문자가 2개 있습니다.

A : 3번 등장, B : 3번 등장. 이는 절대 팰린드롬으로 만들 수 없습니다.

이처럼 홀수번 등장하는 문자가 2개 이상이라면

미안하다고 띄워주면 되겠습니다.

 

홀수번 등장하는 문자가 하나일 때를 보겠습니다.

ex) BBBCCAA

이런 경우 B가 3번 등장하므로 B 한개를 팰린드롬의 가운데에 세워주고

남은 B 두개를 짝수번 등장하는 문자처럼 사용할 수 있습니다.

=> CBABABC 이런 식으로 말입니다. 이와 같이 만들 수 있는건 여러갭니다.

=> ACBBBCA 이런 식으로도 만들 수 있습니다.

 

 

하지만 문제에서는 팰린드롬을 여러개 만들 수 있다면 사전순으로 출력하랍니다.

홀수번 등장하는 문자가 두개 이상이라면 위에서 예외 처리를 했으므로

짝수번 등장하는 문자들을 딕셔너리로 뽑아냅니다.

 

다음 홀수번 등장하는 문자가 한개 있다면 한개를 가운데로 세울 것이고 나머지를

짝수개 등장한 것처럼 사용할 것이기에 짝수 딕셔너리에 넣어줍니다.

 

짝수 딕셔너리를 문자에 대해 정렬하고 반만 출력해 줍니다.

ex) BBBAACC

짝수 : A : 2, B : 2, C : 2 => 이와 같이 정렬됨.

홀수 : B 한개만 사용.

 

A B C => 한번씩만 출력.

A B C B => 홀수개인 문자를 하나 출력해 줍니다.

다음 나머지 짝수들을 역순으로 남은 만큼만 출력해주면 되겠습니다.

A B C B C B A