[문자열 조작] 02 문자열 뒤집기(Reverse String)

<LeetCode 문제>

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

Reverse String - LeetCode

리스트를 뒤집는 문제입니다. 이때, 리턴 없이 주어지는 리스트 내부를 직접 조작해야 합니다.

<풀이>

맨 처음 시도한 코드는 다음과 같습니다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
    	s=s[::-1]

 

기존 리스트가 뒤집힌 리스트의 data가 s에 들어있는 것은 맞지만, 기존 객체가 아닌 새로운 객체가 할당됩니다.

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

#출력
#140538954467520
#140538954467456

 

이때 s가 아닌 s[:]에 할당하면 같은 객체에서 내용이 바뀝니다.

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

#출력
#140054522812352
#140054522812352

 

이 문제는 특이하게 공간복잡도를 O(1)로 제한해서 s=s[::-1]이 아닌 s[:]=s[::-1]로 할당해야 정답 처리됩니다.

 

슬라이싱이 아닌 리스트에 제공되는 reverse() 함수를 이용하여 문제를 풀 수도 있습니다.

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

 

추가로 투 포인터를 이용한 전통적인 방식으로 풀이할 수도 있습니다.

class Solution:
    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

 

투 포인터와 비슷하게 풀이한 저의 방식은 다음과 같습니다.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        for i in range(0,len(s)//2):
            s[i], s[len(s)-1-i] = s[len(s)-1-i], s[i] #교환

 

<학습내용>

1. s[:] = s[::-1]은 같은 객체에서 내용이 바뀌고, s=s[::-1]은 새로운 객체가 할당

 

<학습이 필요한 내용>

1. reverse와 reversed의 차이(https://itholic.github.io/python-reverse-reversed/)

 

https://github.com/HoYoungChun/Algorithm_PS/blob/master/String/LC_344.py

GitHub - HoYoungChun/Algorithm_PS: Baekjoon Online Judge, Programmers problem solving by Python, C++