[Kotlin] 중복 문자열 확인 알고리즘

문제

문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라

 

문제 풀기 전 확인 사항

• 문자열이 ASCII인지 아니면 유니코드인지 확인 필요
• 공백은 

 

문제 풀이1 : Map 자료 구조를 사용한 문제 해결

풀이

만약 문자열이 유니코드로 인코딩되어 있다면, 최대 4바이트이기 때문에 Map 자료 구조를 사용하는 것이 좋다. 

class Solution() {
    fun hasDuplicateCharacter(string : String) : Boolean {
        val map : MutableMap<Char, Boolean> = mutableMapOf()
        for(char in string) {
            char.code
            if(map[char] == true) return true
            else map[char] = true
        }
        return false
    }
}

 

복잡도

문자열의 길이가 N이라고 했을 때 시간 복잡도와 공간 복잡도는 다음과 같다. 

Time Complexity : O(N)
Memory Complexity : O(N)
만약 N이 2^16보다 충분히 크다면 공간 복잡도는 O(1)이 된다.

 

문제 풀이2: Boolean Array를 사용한 문제 해결

풀이

만약 ASCII로 인코딩 되어있고 A-z만 사용한다면, 문자열은 최대 52개가 존재하기 때문에 다음과 같이 풀 수 있다.

A가 ASCII에서 값이므로 아래와 BooleanArray를 만든 다음 확인하는 방식으로. 푼다.

class Solution2() {
    fun hasDuplicateCharacter(string: String): Boolean {
        val usedArray = BooleanArray(52)
        val indexA = 'A'.code
        for (char in string) {
            if(usedArray[char.code - indexA]) {
                return true
            }
            usedArray[char.code - 'A'.code] = true
        }
        return false
    }
}

 

복잡도

문자열의 길이가 N이라고 했을 때 시간 복잡도와 공간 복잡도는 다음과 같다.

Time Complexity : O(N)
Memory Complexity : O(1)