set 자료구조를 활용하여 조건 검사 속도 최적화 - 리트코드 345

https://daelkdev.tistory.com/43

리트코드 - 345. Reverse Vowels of a String

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"]
        l, r = 0, len(s) - 1
        s = list(s)

        while l < r:  # O(n)은 len(s)
            while l < r and s[l] not in vowels:  # O(vowels)
                l += 1
            while l < r and s[r] not in vowels:  # O(vowels)
                r -= 1

            s[l], s[r] = s[r], s[l]  # O(1)
            l += 1
            r -= 1

        return "".join(s)  # O(n)

 

s[l] not in vowels: # O(vowels) 어떻게 하면 이걸 더 최적화 할 수 있을까요? vowels 는 현재 배열입니다. 특정 값이 어떠한 자료구조에 존재하는지 검사할 때 더 좋은 자료구조가 있을까요?

 

vowels 배열에서 특정 값의 존재 여부를 검사하는 부분을 최적화하기 위해, set 자료구조를 사용할 수 있다.

Python에서 set은 해시 테이블을 기반으로 하며, 특정 요소의 존재 여부를 평균적으로 O(1) 시간 복잡도로 검사할 수 있다.

 

해시 테이블은 요소의 해시값을 계산하고 이를 기반으로 해당 요소에 바로 접근할 수 있기 때문이다. 동일한 해시값을 가지는 서로 다른 요소들(충돌)이 있을 수 있다.