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

문제예시

1. 입력

AABB

2. 출력

ABBA

---

1. 입력

AAABB

2. 출력

ABABA

---

1. 입력

ABACABA

2. 출력

AABCBAA

---

1. 입력

ABCD

2. 출력

I'm Sorry Hansoo

---

규칙

1. 팰린드롬은 대칭의 형태를 가진 문자열로 거꾸로 읽어도 원래 순서대로 읽은 문자와 동일한 형태를 가진다

2. 문자열은 가운데를 기준으로 양쪽 문자열이 대칭을 이룬다

3. 만약 동일한 문자의 개수에 대하여 홀수인 개수가 여러개일 경우 해당 문자는 팰린드롬을 만들 수 없다

4. 대칭 문자에 관해 문자열 전체 길이가 홀수인 경우를 제외하면 가운데를 기준으로 모든 각 문자의 전체 갯수는 왼쪽, 혹은 오른쪽의 문자열에 포함된 각 문자의 개수의 * 2다

---

풀이

1. 해쉬를 이용하여 각 문제에 대한 개수를 파악한다 -> 여기서 팰린드롬을 만들 수 있는지 여부를 확인한다
   a. 만약 A, B, C 문자를 저장했을때 각 문자의 개수가 홀수가 되는 경우는 단 하나만 존재해야 한다
   -> 즉, 3개의 문자중 홀수개를 가진 문자는 하나만 있어야 하며, 2개 이상의 문자가 홀수개를 가진 경우 팰린드롬을 만들 수 없다

2. 팰린드롬을 만들 수 있는 경우 해쉬를 "문자 오름차순" 으로 정렬한다

3. 정렬된 해쉬를 순회하면서 각 문자의 개수를 2로 나눈다
   a. 3의 결과로 나온 몫은 문자의 개수는 중심을 기준으로 한쪽 방향(왼쪽 또는 오른쪽)에 들어가는 문자의 개수를 의미한다
   b. 만약 3의 결과와 함께 문자개수가 홀수(문자갯수 % 2 != 0)인 경우 해당 문자가 전체 길이가 홀수인 팰린드롬의 가운데 문자가 된다
   c. 3의 결과로 나온 몫 만큼 stack과 문자열에 문자를 삽입한다

4. 순회가 완료되면 mid를 문자열에 추가한다

5. 이후 stack을 pop하여 모든 문자를 문자열에 삽입한다

---

코드

let input = readLine()!.map { String($0) }
var hash = [String:Int]()
var stack = [String]()
var result = ""
var mid = ""

for i in input {
    if hash[i] == nil {
        hash[i] = 1
    }else {
        hash[i]! += 1
    }
}

if hash.filter({$0.value % 2 != 0}).count > 1 {
    print("I'm Sorry Hansoo")
}else {
    let sortedHash = hash.sorted(by: { $0.key < $1.key })

    for (key, value) in sortedHash {
        let stringCount = value / 2
        
        if value % 2 != 0 {
            mid = key
        }
        
        for _ in 0..<stringCount {
            stack.append(key)
            result += key
        }
    }
    
    result += mid
    
    while !stack.isEmpty {
        result.append(stack.removeLast())
    }
    print(result)
}

최적화 코드

let input = readLine()!.map { String($0) }
var hash = input.reduce(into: [String: Int]()) { $0[$1, default: 0] += 1 }

var result = ""
var mid = ""

if hash.values.filter({ $0 % 2 != 0 }).count > 1 {
    print("I'm Sorry Hansoo")
} else {
    for key in hash.keys.sorted() {
        let stringCount = hash[key]! / 2
        
        if hash[key]! % 2 != 0 {
            mid = key
        }
        
        result += String(repeating: key, count: stringCount)
    }
    
    let reversedResult = String(result.reversed())
    result += mid + reversedResult
    print(result)
}