[프로그래머스 Lv.1] 가장 가까운 같은 글자 (Python)

코딩테스트 연습 - 가장 가까운 같은 글자 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

문제

문자열 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 ≤ s의 길이 ≤ 10,000
s은 영어 소문자로만 이루어져 있습니다.

 

 

입출력 예

s	result
"banana"	[-1, -1, -1, 2, 2, 2]
"footbar"	[-1, -1, 1, -1, -1, -1]

 

 

 

 

---

풀이

 

아이디어: 정규 표현식을 이용하여 각 문자열의 인덱스를 모두 찾아낸다. for문을 돌면서 가장 큰 인덱스에서 두번째로 큰 인덱스를 빼기

import re

def solution(s):
    result = []
    for i in range(len(s)):
        if s[i] not in s[:i]:
            result.append(-1)
        else:
            indices = [match.start() for match in re.finditer(s[i],s[:i+1])]
            max_1=indices.pop()
            gap = max_1 - max(indices) 
            result.append(gap)
    return result

if문에서 이전에 나오지 않은 문자라면 -1을 반환하도록 하고

else문에서 re.finditer()로 s[:i+1]의 범위에서 s[i]가 있는 위치를 모두 찾는다.

pop을 이용해서 가장 큰 값을 뽑아오면서 indices 리스트에서 삭제하고,

그 값을 남은 indices에서 가장 큰 값과 빼주어서 차이를 구한다.

 

 

 

다른 풀이: enumerate()를 2번 이용하여 s의 문자 1개당 앞에서 같은 문자가 나온 인덱스를 모두 모아준다.

def solution(s):
    answer = []
    for a,b in enumerate(s):
        empty=[]
        for i,j in enumerate(s[:a]):    
            if b == j:      
                empty.append(i)
        answer.append(a-max(empty) if empty else -1)
    return answer

바깥의 for문으로 s의 문자 각각을 1바퀴 돌린다.

내부의 for문 범위를 s[:a]로 설정해서 바깥의 b가 도는동안 각각의 b를 자신의 앞 부분 문자들과 비교하도록 하였다.

 

만약 앞부분에 같은 문자가 있다면(b == j)  j가 위치하는 인덱스(i)들을 모아준다.

그리고 삼항 연산자를 사용. empty리스트가 비어있다면 False 이므로 else문이 실행되고, empty가 비어있지 않다면 True 이므로, 원래 b의 인덱스 a 에서 모은 (i)중에서 가장 큰 값을 빼 주어서 차이를 구한다.

 

 

 

 

---

또 다른 풀이

def solution(s):
    answer = []
    dic = dict()
    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()를 사용해서 문자당 인덱스를 모았는데, 이 방법은 딕셔너리를 사용.

 

딕셔너리에 s[i] : i 를 key : value 로 계속 넣어준다.만약 같은 문자가 key로 나오면 바로 기존의 인덱스와 새로운 인덱스의 차이를 빼주면서,해당 문자에 대한 value를 새롭게 업데이트해준다.