문제 링크

프로그래머스 문제

풀이

보자마자 복잡한 문자열에 대해서 빠른 찾아야 하는 알고리즘을 적용시키기 위해서는 hash 를 사용해야 한다는 생각이 들었다.

function solution(gems) {
    var answer = [0, gems.length-1];
     
    const GEMSSIZE = [... new Set(gems)].length

    const gem = {}
    gem[gems[0]] = {
        size : 1,
    }
    
    let leftPtr = 0;
    let rightPtr = 0;
    
    while(rightPtr < gems.length && leftPtr <= rightPtr){
        // 현재 범위에 모든 보석이 있는지,
        // 보석이 있다면, 정답으로 반환한 값과 비교하여, 더 작은 범위의 answer를 반환한다. 
        // 보석이 모두 있다면,leftPtr을 증가시킨다. 
        if(getObjectSize(gem)=== GEMSSIZE){
            if(answer[1] - answer[0] > rightPtr - leftPtr){ // 더 적은 범위라면?
                answer = [leftPtr , rightPtr]
            }
            gem[gems[leftPtr]].size-=1;
            leftPtr++;
        }
        // 보석이 없는지,
        // 보석이 없다면 rightPtr을 증가시킨다. 
        else{
            rightPtr+=1;
            if(gem[gems[rightPtr]]){
                gem[gems[rightPtr]].size++;
            }else{
                gem[gems[rightPtr]] = {
                    size :1
                }
            }
        }
        
    }
    
  
     
    return [answer[0]+1, answer[1]+1];
}

function getObjectSize(object){
    let size = 0;
    for(let val in object){
        if(object[val].size > 0){
            size++
        }
    }
   
    return size
}

하지만 다음과 같은 풀이를 작성하였을때, 효율성 판단 테스트 케이스에서 모두 탈락하였는데,
getObjectSize를 사용할때, 모든 object의 객체를 순회하기 때문이었다.
현재 Object가 가진 gems의 종류를 전역으로 관리해야한다는 생각이 들어 반영하였다.

코드

function solution(gems) {
    var answer = [0, gems.length-1];
     
    const GEMSSIZE = [... new Set(gems)].length
    const gem = {}
    gem[gems[0]] = {
        size : 1,
    }
    
    let leftPtr = 0;
    let rightPtr = 0;
    let gemCount = 1;
    while(rightPtr < gems.length && leftPtr <= rightPtr){
        // 현재 범위에 모든 보석이 있는지,
        // 보석이 있다면, 정답으로 반환한 값과 비교하여, 더 작은 범위의 answer를 반환한다. 
        // 보석이 모두 있다면,leftPtr을 증가시킨다. 
        
        if(gemCount=== GEMSSIZE){
            if(answer[1] - answer[0] > rightPtr - leftPtr){ // 더 적은 범위라면?
                answer = [leftPtr , rightPtr]
            }
            gem[gems[leftPtr]].size-=1;
            if(gem[gems[leftPtr]].size === 0){
                gemCount-=1;
            }
            leftPtr++;
        }
        // 보석이 없는지,
        // 보석이 없다면 rightPtr을 증가시킨다. 
        else{
            rightPtr+=1;
            if(gem[gems[rightPtr]]){
                gem[gems[rightPtr]].size+=1;
                if(gem[gems[rightPtr]].size === 1){ // 여기서 이미 제거가 되었지만 새롭게 size가 1이 된경우 전체 gemCount는 증가시킨다.
                    gemCount+=1
                }
            }else{
                gem[gems[rightPtr]] = {
                    size :1
                }
                gemCount +=1;
            }
        }
        
    }
    
     
    return [answer[0]+1, answer[1]+1];
}