문제
문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라
문제 풀기 전 확인 사항
- 문자열이 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)
반응형
'알고리즘 > 알고리즘' 카테고리의 다른 글
[Kotlin] Matrix 90도 회전시키기 : Matrix Rotation (0) | 2023.05.27 |
---|---|
[Kotlin] String 압축하기 : 반복되는 문자 압축하기 (0) | 2023.05.26 |
[Kotlin] 두개의 String이 있다고 했을 때, 하나의 String에 대해 문자를 하나 이하로 추가하거나 지우거나 다른 값으로 바꾸었을 때 동일한지 확인 (0) | 2023.05.25 |
[Kotlin] String이 Palindrome Permutation인지 확인하기 (0) | 2023.05.24 |
[Kotlin] 공백을 "%20"으로 대체해 Url로 만들기 (0) | 2023.05.23 |