문제
문자열을 뒤집는 함수를 작성하라. 입력값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라.
예제
- 입력
["h", "e", "l", "l", "o"]- 출력
["o", "l", "l", "e", "h"]
문제 분석✍️
이 문제는 리턴 없이라는 단어가 핵심인 문제이다.
리턴이 없는 말은 새로 리스트를 만들지 않고 원래 리스트 내에서 수정하라는 말로 해석할 수 있다.
따라서 for loop을 통해 입력 리스트에서 뒤에서부터 하나씩 가져와 새로운 리스트에 입력하는 방식은 안된다.
책에서는 2가지 방식(투 포인터를 이용한 스왑, 파이썬다운 풀이)으로 풀이하고 있다.
🤔내가 생각한 풀이
문제 풀이를 확인하기 전 내가 생각한 문제 풀이 방식은 다음과 같다.
Step 1: index를 통해 리스트의 가장 앞, 뒤 원소를 지정한다.
이때, 음수를 이용한 indexing 활용
Step 2: 두 원소를 indexing 기능을 이용해 바꾸어 준다.
Ex. s[1] = s[-2], s[-2] = s[1]
s = input() #입력 리스트
for i in range(len(s)):
s[i], s[-i+1] = s[-i+1], s[i]이 풀이는 오류가 발생한다ㅠㅠ
문제 풀이1: 투 포인터를 이용한 스왑
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1 #포인터: left, right
while left < right: #stop 조건: left >= right
s[left], s[right] = s[right], s[left]
left += 1
right -= 1이 풀이는 left, right라는 두 개의 포인터를 설정해 포인터의 위치(책에서는 범위라고 표현)를 조정하며 모든 요소를 확인하며 작업을 진행하는 방식이다.
책에서는 스왑이라는 용어를 사용했다. 리스트 내부를 '스왑'한다는 말은 영어 그대로 swap, 교환한다는 의미이다.
즉, 리스트 요소를 따로 변수를 만들어 저장하는 등의 작업을 하지 않고 단순히 left, right에 할당된 변수를 교환하며 요소의 위치를 바꾼다.
이 방법을 사용하여 문제를 푸는 이유는 리턴없이 바로 문자 위치를 바꿀 수 있기 때문이다.
내가 생각한 풀이처럼 index를 이용하지 않고 포인터를 이용하는 이유는 index를 사용하면 충돌이 발생하거나, 원래 원소가 사라지는 일이 발생할 수 있기 때문이 아닐까 생각한다.
문제 풀이2: 파이썬다운 풀이
def reverseString(self, s: List[str]) -> None:
s.reverse()python 함수: reverse()
.reverse()
: python에서 제공하는 함수로, 입력값이 리스트로 제공될 때 리스트를 뒤집는다.
- 문자열을 뒤집을 때처럼 슬라이싱을 활용([::1])할 수도 있지만 공간 복잡도 측면에서 효율이 떨어진다.
- 슬라이싱 활용법s = s[::1] # 공간복잡도 문제 > 변수 할당 처리에 제약 생김s[:] = s[::-1] #디버깅에 문제 발생할 가능성 있음.
