프로그래머스 | 가장 가까운 같은 글자 (Python3)

 

오늘도 오랑이는 문제를 풉니다. 

 

가장 가까운 같은 글자

 

풀이 과정

문자열 s의 글자 s[i]에 대해 1) 처음 나온 경우와 2) 그 외 두 경우로 나눠서 설계해야 하는 문제입니다. 

def solution(s):
    answer = []
    for i in range(len(s)):
        if : #조건
            answer.append() #가장 가까운 글자와의 자릿수 차이
        else: 
            answer.append(-1)
    return answer

 

처음에는 조건을 'for i in s' 라고 생각했지만 그렇게 되면 전체 범위에 대해 조건이 적용되어 모든 글자에 대해 동일한 값을 출력하게 됩니다. 

그렇기 때문에 더 구체적인 범위를 설정해줘야 합니다. 

 

for i in s[0:i] 즉 문자열 s 안에서 i 까지의 범위에 대해, 인덱스 i - (분절된 문자열의 뒤에서부터 찾은 인덱스값) 의 조건으로 설정합니다. 

for i in range(len(s)):
    if s[i] in s[0:i]:
        answer.append(i - s[0:i].rfind(s[i]))

 

s = "banana" 에 대해 쪼개서 보면 아래와 같습니다. 

i = 3 일 때 s[i] = "a" (두번째 a)

s[0:i] = b a n 

s[0:i].rfind(s[i]) = 1

즉 3 - 1 = 2

 

하지만 막상 이렇게 코드를 짜고 보니 실제 실행시간이 너무 오래 걸린다는 부분을 파악했습니다. 

 

그래서 다른 풀이를 살펴보니 딕셔너리에 값을 저장하고 그거와 일치하는지 확인하고 그 일치하는 값에 대해 조건을 부여하는 형식의 풀이가 있었습니다.

 

바로 살펴봅시다. 

 

빈 딕셔너리 설정은 dic = dict() 혹은 dic = {} 로 미리 해둡니다. 

s[i] 가 딕셔너리에 없을 때, 즉 문자열 s 에서 처음 등장했을 때 -1이 출력되도록 하고,

딕셔너리에 이미 s[i]가 있을 경우, 인덱스 i 에서 딕셔너리 인덱스 dic[s[i]] 을 뺀 값을 출력하도록 합니다. 

그 후 딕셔너리에 저장된 값이 지나간 i 로 재설정 되도록 하는 것이 중요합니다. 

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

 

이때 해당 식을 else 조건문 안에 넣어버렸는데, 이렇게 되면 반복문이 제대로 돌지 않기 때문에 주의하도록 합니다. 

 

최종 코드

def solution(s):
    answer = []
    dic = {}
    for i in range(len(s)):
        if s[i] not in dic:
            answer.append(-1)
        else:
            answer.append(i - dic[s[i]])
        dic[s[i]] = i

    return answer

 

정확성 테스트 시간이 확연히 줄어든 걸 확인할 수 있습니다. 

 

 

이때 enumerate를 사용해서 좀 더 보기 쉽게 풀이한 방법도 있습니다. 

def solution(s):
    answer = []
    dict = {}
    
    for index, word in enumerate(s):
        if word not in dict:
            answer.append(-1)
            dict[word] = index
        else:
            answer.append(index - dict[word])
            dict[word] = index
        
    return answer

 

 

 

오랑우탄이 영어를 하고 오랑이가 코드마스터가 되는 그날까지~

 

 

프로그래머스