[Kotlin] String이 Palindrome Permutation인지 확인하기

문제

String이 주어졌을 때 String이 Palindrome Permutation인지 확인하라

*Palindrome이란 문자열이 좌우 대칭인 경우를 뜻한다. 문자열이 "abcc ba" 일 경우 palindrome이다.

*Permutation이란 문자열의 순서를 바꾸는 것을 뜻한다. 예를 들어 "abc"를 "cba"로 바꾸는 것을 뜻한다.

*Palindrome Permutation은 문자열의 순서를 바꿨을 때 문자가 좌우 대칭(Palindrome)인지 확인하는 것이다. 예를 들어 "aabb cc"일 경우 이 문자열의 순서를 "abccba"로 바꿀 수 있으므로 Palindrome Permutation이다.

문제 풀기 전 확인 사항

1. 대소문자를 구분해야 되는지 확인

2. 띄워쓰기를 문자로 포함해야 되는지 확인

3. empty string일 경우 어떻게 처리해야 하는지 확인

문제 풀이

String이 Palindrome Permutation이려면 각 문자가 2의 배수씩 있어야 하고, 만약 2로 나누었을 때 나머지가 1이 되는 문자가 1개 초과로 있으면 안된다. 

class Solution() {
    fun isPalindromePermutation(string: String) : Boolean {
        val map : MutableMap<Char, Int> = mutableMapOf()
        for(char in string.lowercase()) {
            if(char == ' ') continue
            increaseCount(map, char)
        }
        val oneSize = map.values.filter {
            it % 2 == 1
        }.size

        return oneSize <= 1
    }

    private fun increaseCount(map: MutableMap<Char, Int>, key: Char) {
        val count = map[key]
        if (count == null) {
            map[key] = 1
        } else {
            map[key] = count + 1
        }
    }
}

복잡도

string의 길이가 N이라고 했을 때

시간 복잡도: O(N) - Map에 넣기 위해 N번 반복

공간 복잡도: O(1) - N이 무한히 클 때 사용되는 공간은 문자에 해당하는 공간의 배수로 한정되어 있으므로

테스트 케이스

fun main() {
    val solution = Solution()
    println(solution.isPalindromePermutation("abc c ba")) // 띄워쓰기 무시하므로 true 반환
    println(solution.isPalindromePermutation("abcbaC")) // 대소문자 무시하므로 true 반환
    println(solution.isPalindromePermutation("aba")) // 2로 나누었을 때 1이 되는 경우 1개인 경우 true 반환
    println(solution.isPalindromePermutation("ab")) // 2로 나누었을 때 1이 되는 경우 2개인 경우 false 반환
    println(solution.isPalindromePermutation("")) // 공백일 때 true 반환
}