문제 정의
두 개의 문자열 haystack(전체 문자열)과 needle(찾고자 하는 부분 문자열)이 주어졌을 때, needle이 haystack 안에서 처음 나타나는 인덱스를 찾아야 합니다.
예를 들어, 전체 문자열이 "helloworld"이고 찾으려는 부분 문자열이 "lo"라면, 결과는 3이 됩니다. 이는 "lo"가 인덱스 3부터 시작하기 때문입니다.
C 언어에는 이러한 기능을 수행하는 표준 라이브러리 함수인 strstr()이 존재하지만, 여기서는 이와 동일하게 동작하는 함수를 직접 구현해 보겠습니다.
알고리즘 접근 방법
두 개의 포인터를 활용한 완전 탐색(Brute Force) 방식으로 문제를 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- i := 0, j := 0으로 초기화하고, m := needle의 길이, n := haystack의 길이로 설정합니다.
- m = 0이라면(빈 부분 문자열), 즉시 0을 반환합니다.
- i < n이고 남은 길이(n - i + 1)가 m보다 크거나 같은 동안 다음을 반복합니다.
- haystack[i] == needle[j]라면:
- temp := i로 현재 시작 위치를 저장합니다.
- j < m이고 i < n이며 needle[j] == haystack[i]인 동안 i와 j를 각각 1씩 증가시킵니다.
- j == m에 도달했다면 모든 문자가 일치한 것이므로 temp를 반환합니다.
- 일치하지 않았다면 i := temp + 1로 되돌리고, j := 0으로 초기화합니다.
- 첫 문자가 일치하지 않으면 i를 1 증가시킵니다.
- haystack[i] == needle[j]라면:
- 끝까지 탐색했는데도 찾지 못하면 -1을 반환합니다.
Python 코드 구현
위 알고리즘을 파이썬 클래스로 구현하면 다음과 같습니다.
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
i = 0
j = 0
m = len(needle)
n = len(haystack)
if m == 0:
return 0
while i < n and n - i + 1 >= m:
if haystack[i] == needle[j]:
temp = i
while j < m and i < n and needle[j] == haystack[i]:
i += 1
j += 1
if j == m:
return temp
i = temp + 1
j = 0
else:
i += 1
return -1
haystack = "helloworld"
needle = "lo"
ob1 = Solution()
print(ob1.strStr(haystack, needle))입력
haystack = "helloworld" needle = "lo"
출력
3
복잡도 분석
- 시간 복잡도: O(n × m) — 최악의 경우 haystack의 모든 위치에서 needle 전체를 비교해야 할 수 있습니다. 여기서 n은 haystack의 길이, m은 needle의 길이입니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 포인터 변수만 사용하므로 상수 공간이 필요합니다.
참고: 파이썬 내장 메서드 활용
실무에서는 위와 같은 로직을 직접 작성하는 대신, 파이썬의 내장 문자열 메서드인 find()를 사용하면 한 줄로 해결할 수 있습니다.
def strStr(self, haystack, needle):
return haystack.find(needle)find() 메서드는 부분 문자열이 존재하면 시작 인덱스를, 존재하지 않으면 -1을 반환하므로 본 문제의 요구 사항과 정확히 일치합니다. 다만 코딩 테스트나 학습 목적에서는 알고리즘을 직접 구현하는 것이 중요합니다. 더 나은 성능이 필요하다면 KMP(Knuth-Morris-Pratt) 알고리즘을 적용하여 시간 복잡도를 O(n + m)까지 개선할 수 있습니다.