387. First Unique Character in a String

가장 먼저 등장하는 유일한 문자의 인덱스를 찾는 문제다.

Solution

dictionary를 사용해 해결했다.
1. 딕셔너리에 각 문자의 개수를 저장한다.
2. 다시 반복문을 돌면서 문자의 개수가 1개인, 유일한 문자에 도착하면 해당 인덱스를 반환한다.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        d = {}
        for i in range(len(s)):
            if s[i] not in d: d[s[i]] = 0
            d[s[i]] += 1
        for i in range(len(s)):
            if d[s[i]] == 1:
                return i
        return -1

시간 복잡도

dictionary의 삽입, 탐색 연산은 모두 O(1)이고, 모든 데이터를 두 번 돌기 때문에 시간 복잡도는 O(2n) 이다.

다른 풀이

Conter() 사용

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count=Counter(s)
        for i,j in count.items():
            if j==1: # checking if occurence is 1
                return s.index(i)
        return -1

카운터라는 함수가 있구나...
s.index() 가 O(n) 이므로 이것도 결국에는 O(2n)이긴 하다.

Counter 사용법 및 시간복잡도 정리:
[Python] 데이터의 개수를 알 수 있는 Counter()

47ms

class Solution:
    def firstUniqChar(self, s: str) -> int:
        text = 'abcdefghijklmnopqrstuvwxyz'
        idx = 10**5
        for i in text:
            index = s.find(i)
            if index != -1 and index == s.rfind(i):
                idx = min(idx, index)
        return idx if idx != 10**5 else -1

이게 3배나 빠르다. 왜지?

오! find()와 rfind()로 처음 등장한 위치와 마지막에 등장한 위치를 비교하는 방법이다. 짧은 문자열에서는 효과가 없겠지만 위 코드는 문자가 아무리 길어져도 알파벳 개수만큼만 for문이 돈다!