[LeetCode] 345. Reverse Vowels of a String

문제 : 

 

입력값으로 문자열 s가 주어지고, s에 나타나는 모든 모음들의 순서들을 뒤집어 문자열을 리턴하면 된다

 

이 문제는 TwoPointers를 이용해 풀면 생각보다 풀기 쉽다.

 

아래는 내가 제출해 통과한 코드이다.

 

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        idx = []
        chars = list(s)

        for i, char in enumerate(s):
            if char in vowels:
                idx.append(i)

        left = 0
        right = len(idx) - 1

        while left < right:
            chars[idx[left]], chars[idx[right]] = chars[idx[right]], chars[idx[left]]
            left += 1
            right -= 1

        return ''.join(chars)

 

- 먼저, 문자열을 돌면서 모음인지 아닌지 판별을 해야 하기 때문에, 모음들이 담긴 집합 vowels를 선언해 주었다. 여기서, 루프를 돌면서 if char in vowels를 해주는데, 여기서 리스트가 아니라 집합으로 선언한 이유는 시간 복잡도를 줄일 수 있어서 이다. 리스트는 반복 가능한 객체로써, in list를 호출하면 리스트의 첫번째 요소부터 끝까지 차례대로 검사하여 리스트 안에 특정 값이 있는지 확인한다[O(N)]. 반면, 검색, 삽입, 삭제에 O(1)의 실행 시간을 가지는 해시 테이블로 구현된 파이썬의 집합은 in을 호출 했을때 O(1)의 시간이 소요되므로, set를 사용 해주었다.

 

-이제, 모음이 나타나는 인덱스를 저장할 리스트 idx를 선언해주고,

 

-입력값으로 주어진 문자열 s를 list()를 통해 각 알파벳을 리스트에 하나씩 담아 리스트를 만들어 주었다.

 

- for i, char in enmerate(s): 다시 만난 친구이다. 자주 나오는것 같으니 꼭 기억을 해 놓자! enmerate(s)는 문자열 s의 각 요소와 인덱스를 동시에 참조 할 수 있게 해준다. 이 함수를 호출하면, in 앞에 있는 i, char에는 차례대로 인덱스, 현재 참조중인 요소가 담길 것이다.

 

- 만약, 현재 비교중인 문자가 모음이라면, 선언한 인덱스 배열에 인덱스를 append 해 준다. 여기까지 마치면, 주어진 입력값을 순회하며 모음이 나타나는 모든 인덱스가 idx배열에 담겼을 것이다.

 

- 이제 TwoPointer를 사용하기 위해 left와 right인덱스를 각각 초기화 해 주었다. 지금 보니 left, right보다 start, end가 더 직관적인 이름 인것 같다. 각각은 문자열의 첫번째 인덱스와 마지막 인덱스를 나타낸다.

 

- 이제 left < right가 될때까지 left와 right의 인덱스를 서로 바꿔준다. 바꿔주며 left와 right을 각각 업데이트 해 준다.

 

Two Pointer를 쓰는 문제중 비교적 난이도가 쉬운 문제였다.