Leetcode 344: 문자열 뒤집기

 

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


제약: 공간 복잡도 O(1)

Reverse String - LeetCode

// 입력 예제
["h","e","l","l","o"]

// 출력 예제
["o","l","l","e","h"]

 

 

 

 

 

 

 

---

 

풀이

 

1. 파이썬 다운 방식

 

리스트에 제공되는 파이썬 내장함수 reverse() 함수를 이용하면 손쉽게 뒤집을 수 있다.

def reverseString(self, s):
    s.reverse()

 

 

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

 

문자열의 시작과 끝에 포인터 2개를 두고 포인터의 인덱스에 해당하는 문자끼리 서로 바꿔가면서 왼쪽 포인터는 한칸 전진, 오른쪽 포인터는 한칸 후퇴하면서 계속 바꿔가면 된다. 

 def reverseString(self, s):
 	# 시작 지점과 끝 지점에 포인터를 하나씩 둠
        left, right = 0, len(s) - 1
        while left < right:
        	# 왼쪽 문자와 오른쪽 문자를 스와이프 함
            s[left], s[right] = s[right], s[left]
            # 왼쪽 포인터 한 칸 전진
            left += 1
            # 오른쪽 포인터 한 칸 후퇴
            right -= 1

 

 

3. 문자열 슬라이싱

 

reverse()는 리스트에만 제공되기 때문에 입력값이 문자열인 경우에는 문자열 슬라이싱을 사용할 수 있다.

아래처럼 작성하면 오류가 발생하는데 문제가 공간 복잡도를 O(1)로 제한하고 있기 때문에 변수 할당에 제약이 있기 때문이다.

def reverseString(self, s):
		# 처음부터 끝까지 역순으로 한 칸씩 
        s = s[::-1]

 

 

이 때 다음과 같은 트릭을 사용하면 제대로 작동한다.

 

 

def reverseString(self, s):
        s[:] = s[::-1]

 

 

 

 

 

---

 

 

 

 

+ 문자열 슬라이싱 보충

 

arr[A:B:C]는 index A 부터 B 까지 C의 간격으로 배열을 만들라는 뜻
만약 A가 None 이라면 처음부터 라는 뜻이고
B가 None 이라면 할 수 있는 데까지
마지막으로 C가 None 이라면 한 칸 간격을 의미함

 

>> arr = range(10)
>> arr
[0,1,2,3,4,5,6,7,8,9]
>> arr[::2] # 처음부터 끝까지 두 칸 간격으로
[0,2,4,6,8]
>> arr[1::2] # index 1 부터 끝까지 두 칸 간격으로
[1,3,5,7,9]
>> arr[::-1] # 처음부터 끝까지 -1칸 간격으로 ( == 역순으로)
[9,8,7,6,5,4,3,2,1,0]
>> arr[::-2] # 처음부터 끝까지 -2칸 간격으로 ( == 역순, 두 칸 간격으로)
[9,7,5,3,1]
>> arr[3::-1] # index 3 부터 끝까지 -1칸 간격으로 ( == 역순으로)
[3,2,1,0]
>> arr[1:6:2] # index 1 부터 index 6 까지 두 칸 간격으로
[1,3,5]

# 출처: https://blog.wonkyunglee.io/3 [Wonkyung's blog:티스토리]