Reverse String

알고리즘

문자열을 뒤집자

문제 이해

344. Reverse String - 문제 링크

문제를 해석하고 이해해보자.

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

입력 문자열은 문자의 배열 형태로 주어진다.

입력 배열 그 자체를 수정해야하며, O(1)의 공간 복잡도로 해결해야한다.


문제 풀이

사실 이 문제는 파이썬에서 굉장히 쉽게 풀 수 있다. 파이썬의 리스트에는 리스트를 뒤집을 수 있는 reverse 라는 메서드가 존재하기 때문이다.

따라서 그냥 s.reverse()를 호출하면 문제가 해결된다.

다른 방법으로는 투 포인터를 이용하는 방법이 있다. 왼쪽, 오른쪽에 각각 포인터를 두고 포인터를 점점 중앙으로 이동시키면서 두 포인터가 가리키는 문자를 서로 교환하는 방법이다.

이 방법은 공간 복잡도가 O(1)이며, 시간 복잡도는 O(n)이다.


코드 구현

reverse-string.py
class Solution:
    def reverseString(self, s: list[str]) -> None:
        # 왼쪽 포인터와 오른쪽 포인터 선언
        left = 0
        right = len(s) - 1
 
        while left < right:
            # 왼쪽 포인터와 오른쪽 포인터의 문자를 교환
            s[left], s[right] = s[right], s[left]
            # 각각의 포인터를 중앙쪽으로 한 칸씩 이동
            left += 1
            right -= 1

포인터를 left, right로 선언하고 각각 왼쪽, 오른쪽에서 시작한다. left가 right보다 작은 동안 반복하면서 두 포인터가 가리키는 문자를 교환하고, 포인터를 한 칸씩 중앙으로 이동시킨다.


마무리

이번 문제는 문자열을 뒤집기만 하면 되는 간단한 문제였다. 파이썬에서는 reverse 메서드를 사용하면 쉽게 해결할 수 있지만, 투 포인터를 이용하는 방법도 알아두면 좋을 것 같다.


참고&공부 자료