[파이썬 알고리즘 인터뷰] 2. 문자열 뒤집기

github.com/onlybooks/algorithm-interview

1. 문제: 리트코드 344.Reverse String

문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라

 

2. 내 코드

def reverseString(self, s):
    for i in range(len(s)):
        s.insert(i, s.pop())

 

3. 투 포인터를 이용한 풀이

def reverseString(self, s: List[str]) -> None:
	left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

 

4. 파이썬다운 풀이

def reverseString(self, s: List[str]) -> None:
	s.reverse()

 

5. 배운 점

1) 리스트를 뒤집을 때는 X.reverse() 사용 가능

2) in-place 알고리즘: 공간복잡도가 O(1)로 추가적인 저장공간을 필요로 하지 않는 알고리즘

ex)버블 정렬, 선택정렬은 in-place 알고리즘이지만 병합정렬, 퀵정렬 등은 in-place 알고리즘이 아니다.