문제 개요
하나의 문자열 s와 두 개의 정수 i, j(i < j)가 주어졌다고 가정해 봅시다. 이때 p는 문자열 s를 무한히 반복해서 이어 붙인 문자열입니다. 우리의 목표는 p에서 인덱스 범위 [i, j)에 해당하는 부분 문자열을 찾는 것입니다.
예를 들어, 입력이 s = "programmer", i = 4, j = 8이라면 출력은 "ramm"이 됩니다.
무한 문자열을 실제로 만들 필요는 없습니다. 반복 문자열의 성질을 이용하면 간단하게 해결할 수 있습니다.
접근 방법
핵심 아이디어는 모듈로(%) 연산입니다. 무한히 반복되는 문자열 p에서 t번째 위치의 문자는 원본 문자열 s의 (t mod len(s))번째 문자와 같습니다. 따라서 다음과 같은 단계로 문제를 해결할 수 있습니다.
- 빈 문자열 p를 초기화합니다.
- t를 i부터 j-1까지 순회하면서 다음을 반복합니다.
- s의 (t mod len(s))번째 문자를 p에 이어 붙입니다.
- 완성된 p를 반환합니다.
이 방법은 j - i 길이만큼만 순회하므로, 아무리 큰 인덱스가 주어져도 효율적으로 동작합니다.
구현 예제
class Solution: def solve(self, s, i, j): p="" for t in range(i,j): p+=s[t%len(s)] return p ob = Solution() s = "programmer" i = 4 j = 8 print(ob.solve(s, i, j))
입력
"programmer", 4, 8
출력
ramm
동작 과정 살펴보기
입력 예제를 단계별로 확인해 보겠습니다. 문자열 "programmer"의 길이는 10입니다.
- t = 4일 때: s[4 % 10] = s[4] = 'r'
- t = 5일 때: s[5 % 10] = s[5] = 'a'
- t = 6일 때: s[6 % 10] = s[6] = 'm'
- t = 7일 때: s[7 % 10] = s[7] = 'm'
각 문자를 이어 붙이면 최종 결과는 "ramm"이 됩니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(j - i)입니다. 요청된 구간의 길이에 비례하여 한 번씩만 순회하기 때문입니다. 공간 복잡도 역시 결과 문자열을 저장하기 위한 O(j - i)입니다.