[카카오 인턴] 보석 쇼핑

문제

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

투포인터 문제를 처음 풀다보니 이해가 어려웠다ㅠㅠ
평소에 JavaScript 문법을 최대한 활용하는 것을 좋아하는 편이지만, 알고리즘을 공부할 때에 이해가 안될때가 많아서 기본적인 문법을 사용하였다.

문제를 간단히 설명하면,

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아, 시작 인덱스와 끝 인덱스를 return 하는 문제이다.

이를 위해 보석을 담는 map을 선언하고 투포인터 알고리즘을 사용하기 위해 left와 right 변수를 선언했다. 그리고 총 보석의 갯수 또한 구해주었다.

    let len = new Set(gems).size;
    let map = new Map().set(gems[0],1);
    let left = 0, right = 0;

그리고 while문을 돌면서 알고리즘을 수행한다.

	if(map.size < len){ // 보석이 다 안들어감
            right++; 	// right 를 증가시킨다.
            if(map.has(gems[right])){
                map.set(gems[right], map.get(gems[right])+1);
            }else {
                map.set(gems[right], 1);
            }
        }

만약에 구간 안에 존재하는 보석의 갯수를 map의 크기로 알아낸다. 만약 left와 right 사이 구간내에 모든 보석이 없다면, right를 플러스해 구간을 넓힌다.

	else {  
            if(map.get(gems[left]) === 1){
                map.delete(gems[left]); 
            }else {
                map.set(gems[left], map.get(gems[left])-1);
            }
            left++;
        }

구간내에 모든 보석이 존재한다면 left를 증가 시키며 다른 구간도 확인하고

     if(map.size === len && right - left < answer[1] - answer[0]){
            answer = [left+1, right+1];
        }

모든 보석을 가지고 있는 가장 짧은 구간을 찾아 answer에 넣어준다.

최종코드

function solution(gems) {
    var answer = [1, gems.length];
    let len = new Set(gems).size;
    let map = new Map().set(gems[0],1);
    let left = 0, right = 0;
    
    while(right < gems.length){
        
        if(map.size === len && right - left < answer[1] - answer[0]){
            answer = [left+1, right+1];
        } // 모든 보석을 포함하고, 가장 짧은 구간
        
        if(map.size < len){ 
            right++; 
            if(map.has(gems[right])){
                map.set(gems[right], map.get(gems[right])+1);
            }else {
                map.set(gems[right], 1);
            }
        } else {  
            if(map.get(gems[left]) === 1){
                map.delete(gems[left]); 
            }else {
                map.set(gems[left], map.get(gems[left])-1);
            }
            left++;
        }
    }
    return answer;
}