[JS/Programmers] 67258. 보석 쇼핑

💬 문제

문제 난이도: Programmers Lv.3

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258

❗️접근방법

투 포인터, Map

👆 1차 코드(통과❌)

function solution(gems) {
    const obj = {}
    let uniqueFlag = true;
    for (let i = 0; i < gems.length; i+=1){
        const gem = gems[i];
        if (obj.hasOwnProperty(gem)){
            obj[gem] += 1;
            uniqueFlag = false;
        }
        else obj[gem] = 1;
    }
    if (uniqueFlag) return [1, gems.length];
    let start = 0;
    let end = gems.length - 1;
    let endFlag = true;
    while (start <= end){
        if (obj[gems[end]] - 1 > 0 && endFlag){
            obj[gems[end]] -= 1;
            end -= 1;
         
        }else if(endFlag && obj[gems[end]] - 1 === 0){
            obj[gems[end]] -= 1;
            endFlag = false;
        }else{
            if (obj[gems[start]] - 1 > 0){
                obj[gems[start]] -= 1;
                start += 1;
            }else break;
        }
    }
    return [start+1, end+1]
}

투 포인터
이중 for문을 사용하면 효율성에서 통과되지 못할 것이기 때문에 투 포인터를 사용하는 문제임은 쉽게 알 수 있었다.
다만, 투 포인터를 사용한다고 할지라도 end 포인터가 배열의 마지막까지 순회하며 가능한 전체 경우를 탐색해야 한다는 것을 간과했다.

반례: AAABAACB
위의 코드는 모든 종류의 보석이 나왔을 때 end지점을 픽스한다.
그래서 위의 반례에서 'ABAAC'로 [4,7]을 답으로 리턴할 것이다.
하지만 답은 'ACB' [6,8]이다.
즉, end 지점을 픽시해버리면 안됐던 것이다.

✌️ 2차 코드(정확성 통과✅, 효율성 통과❌)

function solution(gems) {
    const N = new Set(gems).size;
    const lastIdx = {};
    const answer = [1, gems.length];
    for (let i = 0; i < gems.length; i += 1){
        const gem = gems[i];
        lastIdx[gem] = i;
        const target = Object.values(lastIdx);
        if(target.length === N){ // --- 1️⃣
            const temp = [Math.min(...target)+1, i+1];
            if(temp[1] - temp[0] < answer[1] - answer[0]){ // --- 2️⃣
                [answer[0], answer[1]] = [temp[0], temp[1]];
            }
        }
        
    }
    return answer;
}

풀이 방법
1. lastIdx 객체는 보석의 이름을 key로 하고, for문의 i 기준 gems 배열에서 해당 보석의 최신 인덱스를 value로 가지고 있다.
가령, gems = ['a', 'b', 'b', 'c', 'a']라고 하면
i = 0) lastIdx = {'a': 0}
i = 1) lastIdx = {'a': 0, 'b': 1}
i = 2) lastIdx = {'a': 0, 'b': 2}
i = 3) lastIdx = {'a': 0, 'b': 2, 'c': 3}
i = 4) lastIdx = {'a': 4, 'b': 2, 'c': 3}
2. 이때 lastIdx에 모든 종류의 보석이 키로써 포함되면 1️⃣ if문 안으로 들어간다.
3. target은 lastIdx 객체의 값들만 담겨 있는 배열이고, 이때 가장 작은 값을 구하기 위해 Math.min을 한다. 그 인덱스부터 포함해서 모든 종류의 보석을 포함하는 것이기 떄문이다.
4. 답은 보석 시작 인덱스에서 끝 인덱스까지 거리가 짧고, 그 거리가 같다면 시작 인덱스가 작은것을 리턴하는 것이므로 2️⃣으로 비교한다.

시간초과 원인
Math.min을 매 순회마다 하므로 O(N^2)의 시간 복잡도를 가진다.

🤟 3차 코드(통과✅, 다른 사람 풀이 참고)

function solution(gems) {
    const N = new Set(gems).size;
    const gemMap = new Map();
    const answer = [1, gems.length];
    for (let i = 0; i < gems.length; i+=1){
        const gem = gems[i];
        gemMap.delete(gem);
        gemMap.set(gem, i);
        if(gemMap.size === N){
            const cand = [gemMap.values().next().value+1, i+1];
            if (answer[1] - answer[0] > cand[1] - cand[0])
                [answer[0], answer[1]] = [cand[0], cand[1]];
        }   
    }
    return answer;
    
}

Map
Map 객체는 키-값 쌍과 키의 원래 삽입 순서를 기억합니다. 모든 값(객체 및 원시 값 모두)은 키 또는 값으로 사용될 수 있습니다. (출처: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map)
gemMap에 추가되는 순서는 i = 0일때부터 오름차순으로 추가된다.
따라서 gemMap.values().next().value를 하면 gemMap에 값으로 들어있는 인덱스 중 가장 작은 것을 반환한다.
따라서 위의 가장 작은 값을 찾기 위한 순회를 할 필요 없다.

🖖 4차 코드(통과✅, 다른 사람 풀이 참고)

function solution(gems) {
    const N = new Set(gems).size;
    let start = 0;
    let end = 0;
    const gemMap = new Map();// (보석 이름, 보석 빈도수)
    gemMap.set(gems[0], 1);
    const answer = [1, gems.length];
    while(end < gems.length){
        if (gemMap.size === N){
            if (answer[1] - answer[0] > end - start){
                [answer[0], answer[1]] = [start+1, end+1];
            }
            
            gemMap.set(gems[start], gemMap.get(gems[start]) -1);
            if(gemMap.get(gems[start]) === 0)
                gemMap.delete(gems[start]);
            // start를 오른쪽으로 이동
            start+=1;
        }else{
            end += 1;
            const eIdx = gemMap.get(gems[end]);
            gemMap.set(gems[end], eIdx ? eIdx + 1: 1);
        }
    }
    return answer;
    
}

투 포인터
1. start, end 포인터 모두 0에서 시작한다.
2. gemMap이라는 map은 보석 이름을 key로, 보석의 등장 횟수를 value로 갖는다.
3. gemMap에 모든 종류의 보석이 다 들어와 있다면, start 포인터를 오른쪽으로 이동시키며 최대한 end 포인터와의 거리를 좁힌다.
4. gemMap에 모든 종류의 보석이 다 들어와 있지 않다면, end 포인터를 오른쪽으로 이동시키며 모든 종류의 보석이 gemMap에 들어오도록 추가한다.