[level 1]가장 가까운 같은 글자

문제

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

 

 

문제 풀이 접근법1

1) 만약 s[i]가 배열 a에 없다면 a에 s[i]를 추가하고, answer에 -1을 추가한다.

2) 만약 s[i]가 배열 a에 있다면 s[i]와 같은 문자를 찾아 해당 문자의 위치를 t에 저장한다.

3) s[i]의 위치(= i)에서 s[i]와 같은 문자들의 위치를 뺀 값 중 가장 작은 값(=가장 가까운 값)을 찾아 반환한다. 

def solution(s):
    answer = []
    a = []
    t = []


    for i in range(len(s)):
        if s[i] not in a :
            a.append(s[i])
            answer.append(-1)
        
        else:
            for j in range(len(s)):
                if s[i] == s[j] and i != j:
                    t.append(j)
        
            for j in range(len(t)):
                min = i - t[0]
            
                if i-t[j] < min and i-t[j] > 0:
                    min = i-t[j]
                
            answer.append(min)
    return answer

시간 초과 등등..여러 에러가 발생했다. 

 

 

문제 풀이 접근법2

def solution(s):
    answer = []
    a = []
    t = []
    
    for i in range(len(s)):
    
        if s[i] not in a:
            a.append(s[i])
            answer.append(-1)
    
        else:
            for j in range(len(s[:i])):
                if s[i] == list(s[:i])[j]:
                    t.append(i-j)
            answer.append(min(t))

    return answer

위와 같은 문제였다...^_^

 

문제 풀이 접근법3(성공!)

1) {원소:원소의 위치} 형태로 저장할 딕셔너리 a를 선언한다. 

2) 만약 딕셔너리 a에 s[i]가 없다면 딕셔너리 a에 원소:원소의 위치를 추가한뒤, answer에 -1을 추가한다.

3) 만약 딕셔너리 a에 s[i]가 있다면 answer에  s[i]의 위치 i와 해당 원소와 같은 문자의 위치를 뺀 값을 answer에 추가한다. 그 후, 딕셔너리에서 s[i]의 값을 자기 자신으로 업데이트 한다(그 다음에 겹치는 문자가 있다면 자기 자신이 가장 가까운 같은 문자가 되므로)

 

def solution(s):
    answer = []
    a =  {}

    for i in range(len(s)):
    
        if s[i] not in a:
            a[s[i]] = i
            answer.append(-1)
    
        else:
            answer.append(i - a[s[i]]) 
            a[s[i]] = i
            
    return answer