Python으로 문자열의 첫 번째 고유 문자 찾기

문제 개요

주어진 문자열에서 딱 한 번만 등장하는 첫 번째 문자를 찾아야 합니다. 예를 들어 문자열이 "people"이라면, 한 번만 나타나는 가장 앞쪽의 문자는 'o'이며, 이 문자의 인덱스인 2를 반환합니다. 만약 조건을 만족하는 문자가 존재하지 않는다면 -1을 반환합니다.

해결 접근 방법

이 문제는 각 문자의 등장 횟수를 기록하는 빈도수 맵(frequency map), 즉 딕셔너리를 활용하면 효율적으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.

• 문자별 등장 횟수를 저장할 빈도수 맵(딕셔너리)을 생성합니다.
• 문자열의 각 문자 c에 대해 다음을 수행합니다.
  • c가 빈도수 맵에 아직 없다면, 키를 추가하고 값을 1로 설정합니다.
  • 이미 존재한다면, 해당 문자의 카운트를 1 증가시킵니다.
• 문자열을 처음부터 다시 순회하면서, 현재 위치의 문자 빈도가 1이라면 그 인덱스를 즉시 반환합니다.
• 모든 문자를 확인한 후에도 조건을 만족하는 문자가 없다면 -1을 반환합니다.

예제 코드

다음 Python 구현을 통해 동작 방식을 더 자세히 살펴보겠습니다.

class Solution(object):
    def firstUniqChar(self, s):
        """
        :type s: str
        :rtype: int
        """
        frequency = {}
        for i in s:
            if i not in frequency:
                frequency[i] = 1
            else:
                frequency[i] += 1
        for i in range(len(s)):
            if frequency[s[i]] == 1:
                return i
        return -1

ob1 = Solution()
print(ob1.firstUniqChar("people"))
print(ob1.firstUniqChar("abaabba"))

입력

"people"
"abaabba"

출력

2
-1

결과 설명

첫 번째 입력 "people"에서는 'o'가 한 번만 등장하므로 인덱스 2가 출력됩니다. 두 번째 입력 "abaabba"에서는 모든 문자가 두 번 이상 반복되므로 -1이 출력됩니다.

복잡도 분석

이 알고리즘은 문자열을 두 번 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 저장되는 서로 다른 문자의 수에 비례하여 최대 O(n)입니다. 덕분에 문자열 길이가 길어져도 선형 시간 안에 안정적으로 처리할 수 있습니다.