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

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

 

📌 제한 사항

• 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

 

📌 입출력 예

---

추측 의사코드) 

1) 방법

1. 전체 문자열을 잘라 배열을 만든다

2. for문을 전체 문자열을 돌린다.

3. 인덱스 이전의 길이 값을 구한다.

4. 가장 가까운 값의 인덱스를 저장할 변수same_Idx를 정의한다.

5. 길이 값을 -2하여 0부터 지금 인덱스 전까지 for문을 돌려 현재 인덱스와 동일한 문자열의 마지막 인덱스를 받아 same_Idx에 저장한다.

6. 만약 동일한 문자열이 없다면 same_Idx에 -1 저장한다. 

6. for문을 나와 만약 same_Idx = -1

   - 이라면 : 반환할 리스트에 -1을 저장

   - 아니라면 : 현재 인덱스에서 동일한 문자열 인덱스를 뺄셈하여 그 값을 리스트에 저장

7. for문을 나와 저장된 리스트를 반환한다.

 

소스코드) 

* 1차) 실패 : 정확성 10

def solution(s):

    answer_List = []

    for i in range(0,len(s)):
        same_Idx = 0;
        if i == 0:
            answer_List.append(-1)
            continue
            
        for x in range(0,i):
            if s[i] == s[x]:
                same_Idx = x;

        if same_Idx == 0 :
            answer_List.append(-1)
        else :
            answer_List.append(i-same_Idx)

    return answer_List

* 2차) 성공 : 메모리: 11 MB, 시간: 3600.46 ms 

def solution(s):

    answer_List = []
    for i in range(0, len(s)):
        same_Idx = 0
        cnt = 0
        if i == 0:
            answer_List.append(-1)
            continue
            
        for x in range(0, i):
            if s[i] == s[x]:
                cnt += 1
                same_Idx = x

        if same_Idx == 0 and cnt == 0:
            answer_List.append(-1)
        else:
            answer_List.append(i - same_Idx)

    return answer_List

 

 

리뷰) 

1차에서 동일한 문자열이 인덱스를 기본 0으로 잡아주고 있어서 동일한 문자열 인덱스가 0일때랑 동일한 문자열이 없을 때를 구분 못함. 그것을 수정해주니 성공.

근데 테스트 5,7,9,11,30 이 3000ms 이상이 나온다. 더 개선해봐야겠다.