[알고리즘]First non-repeating character

문제

문자가 주어지면 그 중에서 반복하지 않는 첫번째 문자열 찾는 문제

 

풀이 1

s = 'aaabcccdeef'

from collections import defaultdict
# 빈도수 구하기
z = defauldict()
for i in s:
    if z[i]:
        z[i] +=1
    else:
        z[i] = 1
        
# Loop defaultdict to find the first 
for k, v in z.items():
    if v ==1:
        return k

 

풀이 2

x = 'aaaabbbcddeef'

for i in x:
	if x.find(i) == x.rfind(i):
    	return i

str.find() : 가장 작은 인덱스 반환
str.rfind() : 가장 큰 인덱스 반환

 

built-in function 을 사용한 부분이라서 조금 애매하긴 하지만

 

find(), rfind() 모두 time complexity가 O(n) 이라고 하니 괜찮지 않을까 싶어 사용해본 풀이 방법

 

str.find(), str.index() 둘 중에 어떤 걸 써도 큰 상관은 없을 듯한 문제

둘의 가장 큰 차이점은 원하는 문자열의 존재 유무에 따라 갈리는데

find는 문자열이 없을 경우 -1

index는 문자열이 없을 경우 exception 을 반환