[프로그래머스 1단계] 가장 가까운 글자

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

프로그래머스

 

def solution(s):
    answer = []
    checkArr = ''
    for i in s :
        if i in checkArr :
                a = checkArr.rfind(i);
                checkArr += i;
                b = checkArr.rfind(i);
                num = b - a;
                answer.append(num);
        else :
            answer.append(-1)
            checkArr += i;
    return answer

 

checkArr에 해당 i 문자 요소가 없다면 checkArr 문자열에 추가해서 추가하기 전 rfind를 이용해서 문자열에 들어있는 마지막 요소와 추가하고 나서 마지막 요소의 차이를 answer 배열에 넣는 로직으로 처음에 제출을 했다.

 

하지만 이 방법은 효율적이지 못하다. 문자열을 반복적으로 검색하고 넣기 때문에 시간복잡도가 높다.

 

더 효율적인 코드를 짜봤다.

def solution(s):
    answer = []
    lastElmtIdx = {}
    for idx, char in enumerate(s):
        if char in lastElmtIdx:
            answer.append(idx - lastElmtIdx[char]) 
        else:
            answer.append(-1) 
        lastElmtIdx[char] = idx
    return answer

 

enumerate와 딕셔너리로 해당 문자 요소의 마지막 인덱스를 저장하는 것! 로직이 훨씬 간단해졌다.