[Programmers] L1. 가장 가까운 같은 글자 (Python)

---

[문제 링크] 👇

프로그래머스

---

풀이

1️⃣ 문자열 길이 만큼 반복문을 돌린다.

 

2️⃣ 문자열 중 현재 위치 전까지 슬라이싱 한 후, 현재 문자가 슬라이싱 한 리스트에 있는지 확인한다. 

if s[i] not in s[:i]:
	...
else:
	...

• 문자 not in 리스트 : 문자가 리스트에 없으면 True 를 반환
• 문자 in 리스트 : 문자가 리스트에 있으면 True 를 반환

 

3️⃣ 없으면 -1을 결과 리스트에 추가하고, 있으면 문자열에서 현재 위치 이전부터 맨 앞까지 거꾸로 확인한다. 

for j in s[i-1::-1]:

• 리스트[start:end:step] : step 에 -1 을 넣으면 뒤에서부터 슬라이싱을 한다.

 

4️⃣ 뒤에서부터 확인하면서 카운트 하고, 현재 위치와 같은 문자가 나타나면 현재 루프를 중단한다.

 

5️⃣ 그리고 카운트 값을 결과 리스트에 추가한다.

 

Solution

def solution(s):
    answer = []
    for i in range(len(s)):
        cnt = 0
        if s[i] not in s[:i]:
            answer.append(-1)
        else:
            for j in s[i-1::-1]:
                cnt += 1
                if s[i] == j:
                    break
            answer.append(cnt)
    return answer

 

 

개선할 점

주어진 함수는 각 문자의 이전 등장 위치를 찾기 위해 반복문을 사용해 뒤로 거슬러 올라가면서 cnt를 증가시키고 있다. 현재 코드도 올바르게 작동하지만, s의 길이가 길어질 경우 성능상 문제가 발생할 수 있다. 이를 개선할 수 있는 방법은 이전 등장 위치를 기록해두고 바로 접근하는 방식을 사용하는 것이다.

• 각 문자의 이전 등장 위치를 기록하는 딕셔너리를 사용하여, 문자열을 한 번 순회할 때마다 바로바로 이전 등장 위치를 확인하도록 한다.
• 매 문자를 탐색할 때 해당 문자가 이전에 등장한 적이 없다면 -1을, 이전에 등장한 위치가 있다면 그 위치와 현재 위치의 차이를 계산하여 answer에 추가한다.

 

개선한 코드

def solution(s):
    answer = []
    last_seen = {}  # 각 문자의 마지막 위치를 저장하는 딕셔너리
    
    for i, char in enumerate(s):
        if char in last_seen:
            # 이전에 등장했다면, 현재 위치와 이전 위치의 차이를 계산
            answer.append(i - last_seen[char])
        else:
            # 이전에 등장하지 않았다면 -1 추가
            answer.append(-1)
        # 현재 위치를 마지막 위치로 갱신
        last_seen[char] = i
    
    return answer

• last_seen 딕셔너리는 각 문자의 마지막 등장 위치를 저장한다.
• 각 문자의 인덱스를 순회하면서, 딕셔너리에서 이전 등장 위치를 확인하여 필요한 거리를 바로 계산할 수 있다.
• 이렇게 하면 문자열을 한 번만 순회하면서 해결할 수 있어 시간 복잡도가 O(n)으로 줄어들어 효율성이 높아진다.

 

---