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

 

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스

 

 

 

 

✳️ 코드 작성

🤔 코드 아이디어

1. 문자열 s의 각 문자를 차례로 확인
2. 각 문자가 등장할 때마다 그 문자의 마지막 등장 위치를 딕셔너리에 기록
3. 첫 등장 여부 판단 :
   • 문자가 처음 등장한 경우: 결과 리스트 answer에 -1을 추가
   • 문자가 이전에 등장한 경우: 현재 위치에서 그 문자가 마지막으로 등장한 위치를 뺀 값을 answer에 추가
4. 문자가 등장할 때마다 그 문자의 마지막 등장 위치를 딕셔너리에 갱신하고 이후에 같은 문자가 나올 때 그 위치를 참조할 수 있도록 함

 

 

💟 코드 풀이

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

    return answer

 

🟣 answer = []

• answer 리스트는 결과를 저장할 빈 리스트

 

🟣 dic = {}

• dic은 각 문자가 마지막으로 등장한 인덱스를 저장하는 딕셔너리

 

🟣 for문

• enumerate(s)를 사용하여 문자열 s를 인덱스(i)와 문자(ch)로 순회
• 각 문자가 순회될 때마다 두 가지 작업이 동시에 일어남
  • 딕셔너리 조회 : 현재 문자인 ch가 딕셔너리 dic에 있는지 확인하여, 이전에 등장했는지 판단
  • 리스트 업데이트 : 문자 ch가 처음 등장했으면 -1을, 이미 등장한 문자라면 현재 인덱스 i와 마지막 등장 인덱스 dic[ch]의 차이를 계산해 answer 리스트에 추가

 

🟣 if 조건문

• 만약 ch가 딕셔너리 dic에 없다면(즉, 처음 등장한 문자라면), answer에 -1을 추가
• 만약 ch가 이미 등장한 문자라면, 현재 인덱스 i와 마지막으로 등장한 인덱스 dic[ch]의 차이를 answer에 추가
  • 예를 들어, 문자열이 "abcab" 일 때
    • 4번째 문자 a는 이미 첫 번째 위치에서 한 번 나왔으니, 두 번째로 등장한 위치는 i = 3
    • 이때, 첫 번째로 등장한 위치는 딕셔너리 dic['a']에 저장되어 있어요. 그 값은 0
    • 그래서 두 번째로 등장한 a의 위치인 3에서 첫 번째로 등장했던 위치인 0을 빼면 3

answer.append(i - dic[ch])  # 3 - 0 = 3

 

🟣 dic[ch] = i

• 딕셔너리 dic에는 각 문자가 마지막으로 등장한 위치를 저장 
• 새로운 위치에서 그 문자가 등장하면, 그 문자의 마지막 위치를 지금의 위치로 업데이트해야 함
• 즉, dic[ch] = i는 현재 문자가 마지막으로 등장한 위치를 업데이트
  • 예를 들어, 문자열이 "abcab" 일 때
    • 4번째 문자 a가 등장했을 때, 첫 번째로 등장한 위치는 0이었음. 하지만 이제 a가 4번째 자리에 다시 등장했으니, a의 마지막 위치를 dic['a'] = 3으로 업데이트해줘야 함
    • 이 작업을 해줘야 다음에 또 a가 등장했을 때는 바로 직전의 위치와 비교할 수 있음

🔖 이 과정이 필요한 이유

 

1. 문자가 여러 번 등장할 수 있기 때문
   • 같은 문자가 문자열에서 여러 번 나올 수 있음
   • 만약 마지막 등장 위치를 계속 업데이트하지 않으면, 처음 등장했던 위치만 계속 참조하게 됨
   • 그러면 정확한 간격을 계산할 수 없음
2. 최신 위치와 비교해야 하기 때문
   • 현재 위치와 그 문자가 가장 최근에 등장했던 위치 사이의 간격을 계산해야 함
   • 따라서 문자가 나올 때마다 딕셔너리에서 그 문자의 마지막 위치를 최신화하는 것이 중요함

 

 

 

💠 예시

s = "abcab"

 

🔵 작동 과정

• 첫 번째 순회 : i = 0, ch = 'a'
  • 처음 등장하므로 answer = [-1]
  • dic['a'] = 0으로 기록
• 두 번째 순회 : i = 1, ch = 'b'
  
  • 처음 등장하므로 answer = [-1, -1]
  • dic['b'] = 1으로 기록
• 세 번째 순회 : i = 2, ch = 'c'
  
  • 처음 등장하므로 answer = [-1, -1, -1]
  • dic['c'] = 2
• 네 번째 순회 : i = 3, ch = 'a'
  
  • 이미 등장했으므로 현재 위치(3)에서 마지막 등장 위치(0)를 뺀 값 3을 추가하여 answer = [-1, -1, -1, 3]
  • 마지막 등장 위치를 dic['a'] = 3으로 갱신
• 다섯 번째 순회 : i = 4, ch = 'b'
  
  • 이미 등장했으므로 현재 위치(4)에서 마지막 등장 위치(1)를 뺀 값 3을 추가하여 answer = [-1, -1, -1, 3, 3]
  • 마지막 등장 위치를 dic['b'] = 4로 갱신
• 최종 결과는 [-1, -1, -1, 3, 3]