파이썬에서 문자열 뒤집기
문자 배열로 이루어진 문자열이 주어졌을 때, 추가 공간(메모리)을 사용하지 않고 문자열을 제자리(in-place)에서 뒤집어야 한다고 가정해 보겠습니다. 예를 들어 입력이 ['H', 'E', 'L', 'L', 'O']라면 출력은 ['O', 'L', 'L', 'E', 'H']가 되어야 합니다.
해결 접근 방법
이 문제는 투 포인터(Two Pointers) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 두 개의 포인터를 설정합니다: start = 0, end = 문자열 길이 - 1
- start 위치의 문자와 end 위치의 문자를 서로 교환(swap)합니다
- start는 1 증가시키고, end는 1 감소시킵니다
- start가 end보다 작은 동안 위 과정을 반복합니다
예제 코드
다음 구현을 통해 더 자세히 이해할 수 있습니다.
class Solution(object):
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
start = 0
end = len(s) - 1
while start < end:
s[start], s[end] = s[end], s[start]
start += 1
end -= 1
string_1 = ["H", "E", "L", "L", "O"]
ob1 = Solution()
ob1.reverseString(string_1)
print(string_1)
입력
String = ["H","E","L","L","O"]
출력
["O","L","L","E","H"]
동작 원리 및 복잡도
이 알고리즘은 문자열의 양 끝에서부터 포인터를 안쪽으로 이동시키며 문자를 교환하는 방식입니다. 전체 문자열의 절반만 순회하면 뒤집기가 완료되므로, 시간 복잡도는 O(n), 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.
참고로 파이썬에서는 슬라이싱(s[::-1])이나 내장 함수(reversed())로도 문자열을 뒤집을 수 있지만, 이 방법들은 새로운 리스트나 객체를 생성하기 때문에 추가 공간을 사용합니다. 따라서 메모리 사용량을 최소화해야 하는 상황이라면 위와 같은 제자리 교환 방식이 가장 적합합니다.