[String Manipulation] Reverse String

박상길님의 <파이썬 알고리즘 인터뷰>를 보며 문제를 풀고 정리한 것입니다.

1. 문자열 뒤집기 (Reverse String)

문제 출처: https://leetcode.com/problems/reverse-string/

문제

Write a function that reverses a string. The input string is given as an array of characters s.
 
Example 1:
Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]
Example 2:
Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]
 
Constraints:
1 <= s.length <= 105s[i] is a printable ascii character.

Follow up:
Do not allocate extra space for another array. You must do this by modifying the input array in-place
with O(1) extra memory.

 

문제 이해 (사고의 흐름)

1. 문자열을 뒤집는 것은 앞서 <Valid Palindrome> 문제를 풀 때 slicing에서 [::-1]을 이용한 것을 쓰면 되지 않을까. 슬라이싱은 문자열 뿐만 아니라 리스트에서도 사용할 수 있다.

2. 핵심은 '리턴 없이 리스트 내부를 직접 조작'하라는 것과 공간복잡도를 O(1)로 제한한다는 것이다. 

 

그럼 

s = s[::-1]을 하면 될까?

아니다. 이렇게 하면 

>>> s = ["h", "e", "l", "l", "o"]
>>> id(s)
4441009792
>>> s = s[::-1]
>>> s
['o', 'l', 'l', 'e', 'h']
>>> id(s)
4441051456

이렇게 새로운 객체를 참조하게 되므로 공간복잡도가 O(1)이어야 한다는 제약을 만족하지 못한다. 

 

따라서 참조가 아닌 값을 복사하기 위해서 [:] 을 사용하여야 한다. 이 방식은 문자열이나 리스트를 복사하는 파이썬다운 방식이다. 

>>> s = ["h", "e", "l", "l", "o"]
>>> id(s)
4441009792
>>> s[:] = s[::-1]
>>> s
['o', 'l', 'l', 'e', 'h']
>>> id(s)
4441009792

 

 

파이썬의 참조 방식

문자나 숫자와 같은 불변 객체에서)

파이썬은 b = a와 같은 형태로 할당하면 b에 변수의 값이 할당되는 것이 아니라 b 변수가 a 변수를 참조하는 형태가 된다. 

아래의 예제를 보면, b = a 를 통해 a와 b는 동일한 메모리 주소를 가리키게 된다. 

>>> a = 10
>>> b = a

>>> id(a), id(b)
(4550522560, 4550522560)

그러나 b에 새로운 값을 할당하게되면 b변수는 더이상 a 변수를 참조하지 않고, 7이라는 새로운 객체를 참조하게 된다. 

새로운 객체를 참조하므로 b는 a와 다른 메모리 주소를 가지게 되며, 

a 변수의 값은 기존 10에서 7로 변경되지 않는다. 

>>> b = 7
>>> a, id(a), id(b)
(10,4550522560, 4550522564)

리스트와 같은 가변 객체에서)

반면 가변 객체를 참조하고 있다면

>>> a = [1, 2, 3]
>>> b = a

>>> id(a), id(b)
(4441009664, 4441009664)

참조 변수 b에서 값을 조작하는 경우 참조 대상 a의 변수도 변경가능하다. 

>>> b[2] = 5
>>> b
[1, 2, 5]
>>> a
[1, 2, 5]
>>> id(a), id(b)
(4441009664, 4441009664)

그러나 이 경우에도 = 연산자로 재할당을 하게 되면 다른 ID가 된다. 

>>> a = [1, 2, 3]
>>> b = a
>>> id(a), id(b)
(4441009856, 4441009856)
>>> b = [1, 2, 5]
>>> a, id(a), id(b)
([1, 2, 3], 4441009856, 4441009664)

 

첫 번째 풀이

from typing import List


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

 

Reverse를 사용한 풀이

• reverse(): reverse는 리스트에서만 사용가능하다. 

from typing import List


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

 

투 포인터를 이용한 swap

리턴없이 리스트 내부를 직접 조작하라는 제약사항을 통해 swap하는 방식을 생각할 수 있다. 

from typing import List


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