[Python] 프로그래머스 Lv1_가장 가까운 같은 글자

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스

 

• 문자열 s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자의 위치 구하기
• 처음 나와서 자신의 앞에 같은 글자가 없는 경우: -1
• 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자의 위치
  • => 자신보다 몇 칸 앞에 있는지
  • 자신보다 앞에 나온 같은 글자가 여러 개인 경우: 그중 가장 가까운 글자의 위치

제한사항

• 1 ≤ s의 길이 ≤ 10,000
  • s는 영어 소문자로만 이루어져 있음

 

"""
입출력 예시)

s =  "banana" -> [-1, -1, -1, 2, 2, 2]
s =  "foobar" -> [-1, -1, 1, -1, -1, -1]
"""

 

 

 

첫 번째 시도

 

def solution(s):
    s_list = list(s)
    answer = []
    cnt = -1
    for i, s in enumerate(s_list):
        if s not in s_list[:i]:
            cnt = -1
        else:
            matching_s_idx = s_list.index(s, 0, i)
            cnt = i - matching_s_idx
        answer.append(cnt)

    return answer

 

-> 테스트 1) (s = "banana") 실패

# s = "banana"

"""
answer = [-1,-1,-1,2,2,4]
"""

 

=> 자신보다 앞에 나온 같은 글자가 여러 개인 경우, 그중 가장 가까운(가장 마지막에 등장한) 글자의 위치를 구하지 못해서 실패

 

• index()
  • 중복된 값이 있으면 가장 최소의(가장 먼저 등장한) 위치를 리턴

 

 

통과한 코드

 

def solution(s):
    answer = []
    idx_dict = {} # 각 문자마다 가장 마지막으로 등장한 위치를 담은 dict

    for i, w in enumerate(list(s)):
        # 처음 등장한 경우
        if w not in idx_dict:
            answer.append(-1) # 답: -1
            idx_dict[w] = i # idx_dict에 현재 위치 추가
        # 자신의 앞에 같은 글자가 있는 경우 
        else:
            answer.append(i - idx_dict[w]) # 답: 현재 위치 - 가장 마지막으로 등장한 위치
            idx_dict[w] = i # idx_dict에 현재 위치(= 가장 마지막으로 등장한 위치) 추가
        
    return answer

 

-> 딕셔너리를 사용해서 각 문자마다 가장 마지막으로 등장한 위치를 저장하고, 다시 등장할 때마다 업데이트하는 방식으로 해결