1213번: 팰린드롬 만들기

dfs로 풀기 (시간초과 😭)

문제 풀이 아이디어

브루탈포스로 푸는 방법입니다. 주어진 문자열로 만들 수 있는 모든 문자열을 만들어보면서 그 중에 회문을 찾는 방식입니다.

하지만 이 방식은 테스트케이스는 통과할 수 있지만 채점을 해보면 시간 초과가 나옵니다.

코드

import Foundation

// 입력 받기
let input = readLine()!.map { String($0) }.sorted()
	//👉 정렬을 하는 이유는 사전순으로 앞선 팰린드롬부터 만들기 위해서
let length = input.count

// 방문 체크 (순서가 다르면 다른 경우 like 순열)
var visited = Array(repeating: false, count: length)
var result = [[String]]()

// 팰린드롬인지 확인하는 함수
func isPalin(_ array: [String]) -> Bool {
		// 앞뒤를 짝지어 확인하면서 다르면 false를 출력한다.
    for i in 0..<Int(array.count/2) {
        if array[i] != array[array.count - i - 1] { return false }
    }
    return true
}

// dfs 구현
func dfs(now: [String], depth: Int) {
		// 깊이 == 길이일 때 팰린드럼이면 result에 추가
    if depth == length {
        if isPalin(now) { result.append(now) }
        return
    }

    for i in 0..<length {
        if !visited[i] {
            visited[i] = true
            dfs(now: now + [input[i]], depth: depth + 1)
            visited[i] = false
        }
    }
}

dfs(now: [], depth: 0)

if !result.isEmpty {
    print(result[0].reduce("", +))
} else {
    print("I'm Sorry Hansoo")
}

dictionary로 풀기

문제 풀이 아이디어

알파벳의 갯수를 세서 dictionary에 저장합니다. 그리고 그 dictionary를 바탕으로 직접 팰린드롬을 만드는 방법입니다.

만약에 알파벳의 갯수가 홀수인 알파벳이 1개 있다면 그 알파벳을 팰린드롬의 한 가운데 놓아두어야 합니다.

하지만 알파벳의 갯수가 홀수인 알파벳이 2개 이상인 경우는 팰린드롬을 만들 수 없습니다.

코드

import Foundation

// 입력 받기
let input = readLine()!.map { String($0) }

// 알파벳 갯수를 저장할 dictionary
var dict = [String:Int]()

// input을 dict에 갯수만큼 저장
input.forEach { s in
    if dict[s] != nil {
        dict[s]! += 1
    } else {
        dict[s] = 1
    }
}

// 홀수인 key를 저장하는 배열
var odd = [String]()

// key를 순회하면서 홀수인 key를 odd에 저장한다.
for key in dict.keys {
    if dict[key]! % 2 == 1 {
        odd.append(key)
    }
}

// 홀수인 key가 1개가 넘으면 팰린드롬을 만들 수 없으므로 종류
if odd.count > 1 { print("I'm Sorry Hansoo"); exit(0) }

// 결과를 저장할 문자열
var result = ""

// 홀수인 key가 하나 있을 때 그 key를 result은 한 가운데 놓는다.
if odd.count == 1 {
    result = odd[0]
    dict[result]! -= 1 //👉 그리고 -1해서 짝수로 만든다.
}

// key를 알파벳순으로 정렬해서 순회한다.
for key in dict.keys.sorted(by: >) {
    while dict[key]! > 0 { //👉 남은 key가 0개일 때까지
        result = key + result + key //👉 앞뒤로 하나씩 붙이고
        dict[key]! -= 2 //👉 key의 갯수를 2개 뺀다
    }
}

print(result)