문자 스트림 또는 하나의 문자열이 주어졌을 때, 그 안에서 첫 번째로 한 번만 등장하는(비반복) 문자를 찾는 문제를 생각해 봅시다. 예를 들어 문자열이 "people"이라면, 한 번만 나타나는 첫 번째 문자는 'o'입니다. 따라서 해당 문자의 인덱스인 2를 반환해야 합니다. 만약 그러한 문자가 존재하지 않는다면 -1을 반환합니다.
문제 해결 접근 방법
이 문제는 빈도수 맵(frequency map)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 단계는 다음과 같습니다.
- 빈도수를 저장할 맵(dictionary)을 하나 생성합니다.
- 문자열의 각 문자 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
동작 원리 설명
첫 번째 반복문에서 각 문자의 등장 횟수를 모두 계산합니다. 두 번째 반복문에서는 문자열을 처음부터 순서대로 확인하면서, 빈도수가 1인 문자를 만나면 즉시 그 인덱스를 반환합니다. 이렇게 하면 문자열 전체를 두 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도 역시 최대 문자 종류 수에 비례하여 O(n)입니다.
예제에서 "people"은 인덱스 2의 'o'가 처음으로 한 번만 등장하는 문자이므로 2를 반환하고, "abaabba"는 모든 문자가 두 번 이상 등장하므로 -1을 반환합니다.