문자열 처리 알고리즘에서 자주 등장하는 문자열 회전(String Rotation) 문제를 살펴보겠습니다. 길이가 n인 문자열 s가 주어졌을 때, 이 문자열을 왼쪽으로 1칸, 2칸, ... n칸씩 회전시켜 얻을 수 있는 모든 문자열을 구하는 것이 목표입니다.
예를 들어, 입력 문자열이 s = "hello"라면 출력 결과는 다음과 같습니다.
['elloh', 'llohe', 'lohel', 'ohell', 'hello']
각 단계마다 첫 번째 문자가 맨 뒤로 이동하면서 문자열 전체가 한 칸씩 왼쪽으로 밀려나는 방식입니다.
해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 결과를 저장할 빈 리스트
res를 생성합니다. - 문자열의 길이를
n에 저장합니다. - i를 0부터 n-1까지 반복하며 다음 작업을 수행합니다.
- 현재 문자열 s에서 인덱스 1부터 n-1까지의 부분 문자열(두 번째 문자부터 마지막 문자까지)을 추출한 뒤, 첫 번째 문자
s[0]을 뒤에 붙여 새로운 s를 만듭니다. - 회전된 문자열 s를 결과 리스트
res의 끝에 추가합니다.
- 현재 문자열 s에서 인덱스 1부터 n-1까지의 부분 문자열(두 번째 문자부터 마지막 문자까지)을 추출한 뒤, 첫 번째 문자
- 모든 반복이 끝나면
res를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(s):
res = []
n = len(s)
for i in range(0, n):
s = s[1:n] + s[0]
res.append(s)
return res
s = "hello"
print(solve(s))입력
hello
출력
['elloh', 'llohe', 'lohel', 'ohell', 'hello']
동작 원리 상세 설명
위 코드가 어떻게 작동하는지 단계별로 살펴보겠습니다.
- 1회전:
"hello"[1:] + "hello"[0]→"ello" + "h"→"elloh" - 2회전:
"elloh"[1:] + "elloh"[0]→"lloh" + "e"→"llohe" - 3회전:
"llohe"[1:] + "llohe"[0]→"lohe" + "l"→"lohel" - 4회전:
"lohel"[1:] + "lohel"[0]→"ohel" + "l"→"ohell" - 5회전:
"ohell"[1:] + "ohell"[0]→"hell" + "o"→"hello"
n번 회전하면 원래 문자열로 돌아오는 것을 확인할 수 있습니다. 이 방법의 시간 복잡도는 O(n²)이며, 각 회전마다 새로운 문자열을 생성하기 때문에 공간 복잡도 역시 O(n²)입니다.