[알고리즘] 프로그래머스 | 가장 가까운 같은 글자

가장 가까운 같은 글자

답: 

def solution(s):
    answer = []
    a_dic = {}
    for i, alpha in enumerate(list(s)):
        if not alpha in a_dic:
            answer.append(-1)
        else:
            answer.append(i - a_dic[alpha])
        a_dic[alpha] = i            
    return answer

 

 

문제 분석 및 해석

문자열 s가 주어질 때

s의 알파벳이 처음 나왔을때는 -1, 이전에 있었던 알파벳이면 index의 차이를 배열에 더해 return하는 문제

 

 

 

>> 풀이생각

1. stack을 쌓기, stack에 없으면 -1

2. -1번에 있으면 1 -2번에 있으면 2... while문으로 처리해보자

   단점 :

   >> if not 요소 in stack(X) 모든 요소를 stack에 넣어야함.

   >> 해당 요소가 첫 값이라는 것을 찾기 위해 stack을 모두 순회해야함

 

   

혹은 글자를 dictionary에 저장해주고 그때그때 해당 index를 연산해주기

1. 없으면 dictionary에 생성하고 해당 index value로 저장

2. 있으면 dictionary에서 찾아서 현재 idx - value

   + dictionary value값 업데이트

 

 

 

 

리뷰.

2가지 풀이를 생각해보았는데, stack으로 풀이하면 문제점이 존재해 dictionary로 풀이했다.

 

 

 

++

dictionary에 요소를 추가할 때

else문에서는 위치가 중요하지만(index값 구하고 나서 업데이트) if문에서는 그다지 중요하지 않다.

따라서 dictionary 업데이트를 if문 바깥으로 빼어 한줄 줄일 수 있음:)

 

수정 전

if not alpha in a_dic:
    a_dic[alpha] = i
    answer.append(-1)
else:
    answer.append(i - a_dic[alpha])
    a_dic[alpha] = i

 

 

수정 후

if not alpha in a_dic:
    answer.append(-1)
else:
    answer.append(i - a_dic[alpha])
a_dic[alpha] = i