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

2023. 5. 24. 21:27·알고리즘/알고리즘
반응형

문제

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 반환
}

 

반응형

'알고리즘 > 알고리즘' 카테고리의 다른 글

[Kotlin] Matrix 90도 회전시키기 : Matrix Rotation  (0) 2023.05.27
[Kotlin] String 압축하기 : 반복되는 문자 압축하기  (0) 2023.05.26
[Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인  (0) 2023.05.25
[Kotlin] 공백을 "%20"으로 대체해 Url로 만들기  (0) 2023.05.23
[Kotlin] 중복 문자열 확인 알고리즘  (0) 2023.05.21


'알고리즘/알고리즘' 카테고리의 다른 글
  • [Kotlin] String 압축하기 : 반복되는 문자 압축하기
  • [Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인
  • [Kotlin] 공백을 "%20"으로 대체해 Url로 만들기
  • [Kotlin] 중복 문자열 확인 알고리즘
심플코드
심플코드
프로그래밍을 어렵지 않게 풀어서 설명하는 기술 블로그
    반응형
  • 심플코드
    심플코드
    심플코드
  • 전체
    오늘
    어제
    • 분류 전체보기 (96)
      • 안드로이드를 위한 Coroutines (2)
      • Unit Testing (19)
      • GitHub Actions (0)
      • 공식 문서 번역 (35)
        • Coroutines 공식 문서 (35)
      • 알고리즘 (7)
        • Kotlin 자료구조 (0)
        • 알고리즘 (7)
        • Kotlin으로 구현하는 자료구조 (0)
      • 코딩 테스트 (0)
      • Deep Learning (0)
      • Machine Learning Math (17)
        • Linear Algebra (17)
      • ML (0)
      • Docker (15)
      • Kubernetes (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

    • 코틀린 코루틴의 정석 책 출간 소식
  • 인기 글

  • 태그

    numpy
    Coroutines
    coroutine
    unit testing
    도커
    TensorFlow
    Machine Learning
    컨테이너
    pytorch
    Coroutines Channel
    코루틴 Flow
    Coroutines Flow
    코루틴
    junit
    mockito
    코루틴 채널
    Coroutines Context
    Docker
    Kotlin
    unit test
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
심플코드
[Kotlin] String이 Palindrome Permutation인지 확인하기
상단으로

티스토리툴바