[Programmers] 가장 가까운 같은 글자

문자열 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]가 됩니다.

개요

레벨이 낮은 문제임에도 불구하고 어떻게 풀어나갈지 아이디어가 바로 떠오르진 않았다. 잠시 고민하고 나서의 풀이 계획은 대략 다음과 같이 잡고 풀어나갔다.

1. 입력받은 문자열을 뒤집는다. banana -> ananab
2. 뒤짚은 문자열의 탐색 부분을 분리한다
- 예를 들어 시작 위치가 a라면 나머지는 nanab 와 같이 이중 for문을 이용하여 범위를 조정해나간다.
3. 시작 위치와 정의해놓은 범위에서 문자가 일치한 경우 인덱스 위치를 계산해 절대값을 씌워 answer에 담아준다.

 

Solve

def solution(s):
    answer = [-1] * len(s)
    length = len(s) - 1

    rev = strings[::-1]

    for i, v in enumerate(rev, start=0):

        for j in range(i + 1, length + 1):
            if rev[i] == rev[j]:
                answer[length - i] = abs(j - i)
                break

    return answer

 

 

Result