[프로그래머스] 보석쇼핑 - 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
Author And Source
이 문제에 관하여([프로그래머스] 보석쇼핑 - javsacript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/프로그래머스-보석쇼핑-javsacript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)