파이썬으로 문자열에서 첫 번째 반복 문자의 인덱스 찾기

문자열 s가 주어졌을 때, 이 문자열에서 가장 먼저 반복해서 등장하는 문자의 인덱스를 찾아야 합니다. 만약 반복되는 문자가 하나도 없다면 -1을 반환하면 됩니다.

예를 들어 입력이 "abcade"라면 출력은 3입니다. 왜냐하면 첫 번째 문자 'a'가 인덱스 3에서 다시 나타나기 때문입니다.

해결 접근 방법

이 문제는 해시맵(딕셔너리)을 활용하면 효율적으로 풀 수 있습니다. 문자열을 왼쪽부터 오른쪽으로 순회하면서 이미 본 적 있는 문자인지 확인하는 방식입니다.

• 등장한 문자를 기록하기 위한 맵(map)인 chars를 정의합니다.
• i를 0부터 s의 길이 - 1까지 순회하며 다음을 수행합니다.
  • 만약 s[i]가 이미 chars에 존재한다면, 해당 인덱스 i를 반환합니다. (첫 번째 반복 문자 발견)
  • 그렇지 않다면, chars[s[i]]의 값을 1 증가시켜 해당 문자를 기록합니다.
• 순회가 끝날 때까지 반복 문자를 찾지 못했다면 -1을 반환합니다.

구현 예제

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

from collections import defaultdict
class Solution:
    def solve(self, s):
        chars = defaultdict(int)
        for i in range(len(s)):
            if s[i] in chars:
                return i
            else:
                chars[s[i]] += 1
        return -1
ob = Solution()
print(ob.solve("abcade"))

입력

"abcade"

출력

3

코드 설명 및 시간 복잡도

위 코드에서는 collections 모듈의 defaultdict를 사용하여 각 문자의 등장 여부를 추적합니다. 문자열을 한 번만 순회하면서 각 문자에 대해 딕셔너리 조회와 저장 작업을 수행하므로, 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 여기서 n은 문자열의 길이입니다.

이 방식은 단순히 각 문자에 대해 앞부분을 다시 탐색하는 브루트 포스 방식(O(n²))보다 훨씬 효율적이므로, 실무에서도 널리 사용되는 패턴입니다.