백준 - 팰린드롬 만들기(Swift)

백준 - 팰린드롬 만들기(Swift)

 

 

 문제 설명

 

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

1213번: 팰린드롬 만들기

 

 

 

 나의 풀이

 

회문을 검사하는 방법은 알고있었지만 회문을 만드는 방법은 잘 와닿지않았다. 

 

우선 짝수만 있을때는 100% 회문을 만들 수 있고, 홀수가 포함될때는 홀수인 알파벳이 한 종류일때만 가능하다는 것 까지는 알았다.

 

즉 AABBC는 ABCBA로 가능하지만 AABBCD는 불가능하다.

 

하지만 이를 어떻게 구현해야할지 고민을 하다가 다른사람의 풀이를 보고 홀수를 가운데 짝수를 양쪽에 배치하면 되는 것을 알았다.

 

또 재밌었던 것은 정답이 여러개일때는 사전순으로 출력해야하기 때문에 key가 큰값부터 정렬해서 큰값부터 나가게 하는 것이였다. 

 

 

import Foundation

var dic:[String: Int] = [:]
let strArr = readLine()!.map{String($0)}
// 알파벳이 쓰인 개수를 삽입
for x in strArr {
    if dic[x] == nil {
        dic[x] = 1
    } else {
        dic[x]! += 1
    }
}
// 홀수의 개수를 담을 배열
var odd: [String] = []
for key in dic.keys {
    if dic[key]! % 2 == 1 {
        odd.append(key)
    }
}

// 알파벳이 홀수인 경우가 1개이상이라면 종료
if odd.count > 1 { print("I'm Sorry Hansoo"); exit(0)}

var result = ""
// 홀수를 가운데 배치
if odd.count == 1 {
    result += odd[0]
    dic[odd[0]]! -= 1
}

// 알파벳을 큰 순서대로 배치함으로써 가장 바깥족엔 제일 작은 것을 배치
for key in dic.keys.sorted(by: >) {
    while dic[key]! > 0 {
        result = key + result + key
        dic[key]! -= 2
    }
}

print(result)