[Python/LeetCode] 344. Reverse String

https://leetcode.com/problems/reverse-string/description/

문자열을 뒤집는 함수를 작성하시오.

입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라.

---

입출력 예시 : 

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

 

---

처음 시도

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s = s[::-1]

그러나, 채점기에 전달된 s는 수정되지 않음.

GPT) 이 코드는 s를 뒤집은 새로운 리스트를 생성하여 s 변수에 할당합니다. 하지만 이 작업은 원래의 s 리스트를 수정하는 것이 아니라 새로운 객체를 생성하고 s 변수를 해당 객체로 재할당하는 것입니다.

이로 인해 호출자에게 전달된 원래의 리스트 s는 수정되지 않고, 결과적으로 문제의 요구사항을 충족하지 못합니다.

즉, 채점기가 참조중인 s가 아닌 다른 id()를 가진 s를 생성한 거니까...

 

또는, 이 문제는 O(1)의 공간 복잡도로 제한되어있다 보니 새로운 변수 s 할당이 안됨.

 

둘 중 어느 요인때문에 틀렸는지는 모르겠으나, 뭐 둘다일 수도? 문제 출제자가 어떻게 설정해놨느냐에 따라 다를듯.

결국, 제자리(in-place) 연산을 수행하는 방식으로 구현해야함.

 

투 포인터

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

이 문제의 기본적인 풀이는 투 포인터 풀이임. 리스트를 새로 만드는 게 아닌, 리스트 내부를 조작해야 하기 때문. 즉, 슬라이싱 없이 양쪽 끝에서 교환하는 방식으로 구현해야 함. 이를 위해 투 포인터(two-pointer) 방식을 사용.

: 두 개의 포인터를 사용하는 방식

시간 복잡도: O(n)

* 참고) 파이썬의 다중 할당 방식

다중 할당의 동작 방식

s[left], s[right] = s[right], s[left]

위 코드에서의 동작은 다음과 같습니다:

1. 오른쪽 값 평가: s[right]와 s[left]가 먼저 평가되어 임시 저장소에 저장됩니다.
2. 왼쪽 값 할당: 임시 저장소에 저장된 값을 s[left]와 s[right]에 각각 대입합니다.

따라서 s[left]가 먼저 변경되어도, s[right]의 값은 이미 임시 저장소에 저장되어 있어 영향을 받지 않습니다.

파이써닉한 방식 - s.reverse() 메서드 사용

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

reverse() 메서드는 리스트에만 제공됨. 문자열에는 없음.

문자열을 뒤집는 방법에 대해선, https://cuffyluv.tistory.com/117 참고.

 

reverse() 메서드 또한 투 포인터를 이용한 스왑과 같은 방식으로 내부 구현돼있음. 내부가 좀 더 최적화돼있다보니 투 포인터보단 아주 살짝 빠르게 나옴.

---

해당 글은 "파이썬 알고리즘 인터뷰(박상길)"을 공부한 내용과 책의 코드가 포함되어 있습니다.

https://github.com/onlybooks/python-algorithm-interview/tree/master