[파이썬 알고리즘] 문자열 뒤집기

문자열 뒤집기

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

해당 문제의 제약조건은 공간 복잡도가 중점인데, O(1)이다.

따라서 전 문제에서 살펴본 흔히 생각할 수 있는 풀이인 슬라이싱을 활용하면 코딩 테스트를 보는 환경에 따라 오답 처리가 될 수 있다.

s = s[::-1]

아마 문자열의 슬라이싱을 내부적으로 처리하는 과정에서 변수를 따로 할당하게 되어 제약에 걸리는것 같다.

s[:] = s[::-1]

다음과 같은 트릭을 사용하면 잘 동작한다고 한다.

이 문제의 답은 크게 두가지이다.

1. 투 포인터를 이용한 스왑

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

2. 파이썬의 내장함수 사용 -> string.reverse( ) 사용