[프로그래머스] 보석쇼핑 - javsacript

📌 문제

https://programmers.co.kr/learn/courses/30/lessons/67258

📌 풀이

function solution(gems) {
  var answer = [];
  let hash1 = new Map();
  let hash2 = new Map();
  for (let i = 0; i < gems.length; i++) {
    hash1.set(gems[i], (hash1.get(gems[i]) || 0) + 1);
  }
  let correct_size = hash1.size; // 보석의 모든 종류

  // 투포인터 실행
  let left = (cur = 0);
  let len = 100001;
  for (let right = 0; right < gems.length; right++) {
    hash2.set(gems[right], (hash2.get(gems[right]) || 0) + 1);
    while (hash2.size >= correct_size) {
      if (right - left < len) {
        answer[0] = left + 1;
        answer[1] = right + 1;
        len = right - left;
      }

      hash2.set(gems[left], (hash2.get(gems[left]) || 0) - 1);
      if (hash2.get(gems[left]) <= 0) {
        hash2.delete(gems[left]);
      }
      left++;
    }
  }
  return answer;
}

✔ 사용한 알고리즘 : 투포인터 + Hashing

✔ hash1은 Map()으로 선언하여 보석의 모든 종류를 hash1.size로 체크

✔ gems 의 시작점을 left,right로 설정하고 투포인터로 순회

✔ hash2.size와 correct_size가 같으면 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 구간이 되므로 길이 비교하여 작은값 answer에 저장

✔ 가장 짧은 구간을 구해야하므로 hash2.size가 같은순간부터 left를 하나씩 증가하며 정답 조건이 맞는지 확인하고 맞으면 구간길이 비교

✔ hash2에서 gems[left]가 0이 되는 순간 hash2에서 해당하는 보석 제거

✔ 난이도 : 프로그래머스 기준 LEVEL 3