문제 이해하기
하나의 텍스트 문자열(text)과 단어 목록(words)이 주어졌을 때, 부분 문자열 text[i]...text[j]가 words 목록에 포함되는 모든 인덱스 쌍 [i, j]를 찾는 문제입니다.
예를 들어 문자열이 "ababa"이고 words 배열이 ["aba", "ab"]라고 한다면, 출력은 [[0,1], [0,2], [2,3], [2,4]]가 됩니다.
여기서 한 가지 눈여겨볼 점은 매칭 결과가 서로 겹칠 수 있다는 것입니다. 위 예제에서 "aba"는 시작 인덱스 0에서 한 번([0,2]), 그리고 다시 인덱스 2에서 한 번([2,4]) 총 두 번 매칭됩니다.
해결 전략
가장 직관적인 방법은 가능한 모든 시작 위치와 끝 위치의 조합을 확인하는 브루트포스(Brute Force) 방식입니다. 알고리즘은 다음과 같이 진행됩니다.
- 결과를 담을 빈 리스트(res)를 생성합니다.
- i를 0부터 문자열 길이 - 1까지 반복합니다.
- j를 i + 1부터 문자열 길이까지 반복합니다.
- 인덱스 i부터 j까지의 부분 문자열이 words에 존재한다면, 결과 배열에 (i, j - 1)을 추가합니다.
- j를 i + 1부터 문자열 길이까지 반복합니다.
- 모든 탐색이 끝나면 결과 배열을 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작 과정을 더 잘 이해할 수 있습니다.
class Solution(object):
def indexPairs(self, text, words):
result = []
for i in range(len(text)):
for j in range(i+1,len(text)+1):
if text[i:j] in words:
result.append([i,j-1])
return result
ob1 = Solution()
print(ob1.indexPairs("ababa",["aba","ab"]))입력
"ababa" ["aba","ab"]
출력
[[0,1],[0,2],[2,3],[2,4]]
복잡도 분석
문자열 길이를 n이라 할 때, 모든 (i, j) 조합은 O(n²)개가 존재하고 각 조합마다 부분 문자열 추출 및 words 검색이 이루어지므로, 전체 시간 복잡도는 대략 O(n³) 수준입니다. 따라서 이 방식은 문자열 길이가 짧은 경우에 적합하며, 입력 크기가 커진다면 트라이(Trie) 자료구조 등을 활용해 검색 효율을 개선하는 것이 좋습니다.