[파이썬 알고리즘 인터뷰] 2. 문자열 뒤집기 (leetcode 344)

leetcode 344. Reverse String

Reverse String - LeetCode

 

문제

 

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

 

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"]

 

내 풀이

 

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

 

이 문제를 봤을 때 떠올랐던 생각은 저번 1번에서 슬라이싱, 리스트 reverse(), reversed() + join(), for 반복, while 반복, 재귀 등을 쓴 파이썬 문자열 처리 실행시간 표가 떠올랐다. reverse() 함수를 썼더니 간단하게 해결하였다.

 

 

---

책 풀이1 - 투 포인터를 이용한 스왑

 

투 포인터 : 2개의 포인터를 이용해 범위를 조정해가며 풀이하는 방식

리턴 없이 리스트 내부를 직접 조작하라 -> s 내부를 스왑하는 형태로 풀이

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

 

책 풀이2 - 파이썬다운 방식

 

reverse() 함수 이용

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

 

원래 s = s[::-1] 도 되는데 이 문제의 경우에는 공간 복잡도를 O(1)로 제한해서 오류뜸

s[:] = s[::-1] 로 하면 잘 동작한다. 

 

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

 

 

<참고>

책 : 파이썬 알고리즘 인터뷰

책 풀이 코드 출처

 

GitHub - onlybooks/python-algorithm-interview: <파이썬 알고리즘 인터뷰> 95가지 알고리즘 문제 풀이로 완성