FirstNotRepeatingCharacter

koeyhoyh·2021년 12월 5일
0

Algorithm

목록 보기
3/16


Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.


Example

For s = "abacabad", the output should be
solution(s) = 'c'.

There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.

For s = "abacabaabacaba", the output should be
solution(s) = '_'.

There are no characters in this string that do not repeat.


Input/Output

[execution time limit] 4 seconds (py3)

[input] string s

A string that contains only lowercase English letters.

Guaranteed constraints:
1 ≤ s.length ≤ 105.

[output] char

The first non-repeating character in s, or '_' if there are no characters that do not repeat.


문자열에서 :
중복되지 않는, 그 중에서 가장 빠른 index를 가진 알파벳을 구해내는 문제이다.


처음 나의 생각 :

  1. 문자열을 dict 형으로 바꾸어 개수를 지정해준다.

ex) a : 1, b : 2 이런 식으로

  1. dict에서 X : 1 인 것만 뽑아서, 다시 한 번 반복문으로 최소 값을 찾아준다.

  2. 1인 값이 있었다면 return char, 없다면 return '_'

코드 :

def solution(s):
    
    mydict = {}
    min_value = 100000
    for char in s :
        if mydict.get(char) == None :
            mydict[char] = 1
        else :
            mydict[char] += 1
            
    for key in mydict :
        if mydict[key] == 1 :
            if s.index(key) < min_value :
                min_value = s.index(key)
                
    
    if min_value == 100000 :
        return "_"
        
    else :
        return s[min_value]

시간 내에 잘 풀렸다.


모범 답안 :

def solution(s):
    for c in s:
        if s.index(c) == s.rindex(c):
            return c
    return '_'

rindex() 나 rfind()를 이용해 푼 정답들이 상위권에 올랐다.

rindex(), rfind()는 끝에서부터 index를 반환해주는 메소드이다.

그러나 rindex()는 해당 원소가 없을 경우 error를 , rfind()는 -1을 return 한다.


사실 이러한 메소드에 대해 모르고 있었는데
rindex(), rfind()에 대해 알 수 있었다.

문제를 풀다보니 내가 모자란 점도 알 수 있고, 더 알고싶어진다. 무엇보다 꾸준히 해보아야겠다.

profile
내가 만들어낸 것들로 세계에 많은 가치를 창출해내고 싶어요.

0개의 댓글