[Javascript] 프로그래머스 - 가장 가까운 글자

문제 설명

주어진 문자열 s에서 각 문자의 가장 가까운 같은 글자와의 거리를 계산하는 문제입니다.

• 문자열을 왼쪽에서 오른쪽으로 순회하며, 이전에 등장한 같은 문자의 위치와 현재 위치의 차이를 계산합니다.
• 이전에 같은 문자가 없으면 결과는 -1로 표시합니다.
• 예를 들어, 문자열 s = "banana"가 주어지면 결과는 [-1, -1, -1, 2, 2, 2]가 됩니다.

---

제한사항

1. 문자열 길이: 1 ≤ s.length ≤ 10,000
2. 문자열 구성: 영어 소문자로만 이루어져 있습니다.

---

해결 방법

알고리즘: 해시맵을 활용한 효율적 탐색

1. 데이터 구조 초기화
   • 각 문자의 마지막 등장 위치를 저장할 해시맵(Map 객체)을 생성합니다.
2. 문자열 순회
   • 문자열을 순회하며 각 문자의 인덱스를 확인합니다.
   • 이전 위치 확인: 해시맵에 문자가 이미 존재하면, 현재 위치와 저장된 위치의 차이를 계산합니다.
   • 초기 등장 처리: 해시맵에 문자가 없으면 -1을 결과에 추가합니다.
3. 위치 업데이트
   • 현재 문자의 위치를 해시맵에 업데이트하여 이후 비교에 활용합니다.
4. 결과 반환
   • 계산된 거리 배열을 반환합니다.

---

시간 복잡도

1. 문자열 순회:
   • 문자열을 한 번 순회하므로 O(n), n은 문자열의 길이입니다.
2. 해시맵 조작:
   • 각 문자의 해시맵 접근 및 업데이트는 O(1)입니다.
3. 총 시간 복잡도: O(n)

---

구현 코드

function solution(s) {
  const map = new Map();
  const answer = Array.from(s).map((item, index) => {
    if (!map.has(item)) {
      map.set(item, index);
      return -1;
    } else {
      const dist = index - map.get(item);
      map.set(item, index);
      return dist;
    }
  });

  return answer;
}