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

문제 링크

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

첫 트라이

일단 무식하게..
첫 인덱스부터 순회하여 만족되는 구간중 최단구간을 구했다.
2중for문이라 뻔히 시간초과될걸 알았지만.. 허헣

function solution(gems) {
    var answer = [];
    const db = new Set(gems);
    if (db.size === 1) return [1, 1]

    gems.forEach((gem, idx) => {
        const visit = {};
        [...db].forEach(el => visit[el] = 1);
        visit[gem] = 0;

        var targetLen = db.size - 1, nextIdx = idx;
        for (; nextIdx < gems.length; nextIdx++) {
            const target = gems[nextIdx];
            if (visit[target]) {
                targetLen--;
                if (targetLen === 0) break;

                visit[target] = 0;
            }
        }
        if (!targetLen) answer.push([idx + 1, nextIdx + 1]);
    })
    return answer.reduce((ac, v) =>
        ac[1] - ac[0] > v[1] - v[0] ? v : ac, [1, gems.length]);
}

다시 풀이

슬라이딩 윈도우 알고리즘
이론상 O(n)

1. 순차적으로 윈도우를 확장해간다.

   AA BB BB AA AA CC DD AA
   AA: 1, BB: 2

2. 중복이 발생할 때 index를 덥어 씌운다.

   AA BB BB AA AA CC DD AA
   AA: 1, BB: 3

3. 조건에 만족되면 알맞은 형태로 정답후보로 변경 -> 정답과 비교

   AA BB BB AA AA CC DD AA
   AA: 5, BB: 3, CC: 6, DD: 7 -> [3, 7]
   AA BB BB AA AA CC DD AA
   AA: 8, BB: 3, CC: 6, DD: 7 -> [3, 8]

function solution(gems) {
    const cnt = new Set(gems).size;
    const gemMap = {};
    var answer = [1, gems.length];
    gems.forEach((gem, i) => {
        gemMap[gem] = i;
        const target = Object.values(gemMap);
        if (target.length === cnt) {
            const cand = [Math.min(...target) + 1, i + 1];
            answer = answer[1] - answer[0] > cand[1] - cand[0] ? cand : answer;
        }
    })
    return answer;
}

전개연산자... 와 Math.min, Object.values로 배열 길이를 구하는 과정이 생각보다 많이 무거운 것 같다.

최종코드

다른 분들처럼.. Map 객체를 써서 쉽게 size를 구할 수 있고
Map은 삽입 순서를 유지해주기에 min 비교연산이 필요 없다.

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

Map을 애용하도록 하자..

코드 추가

공식 문제 해설을 참고하여 다시 작성해봤다
https://tech.kakao.com/2020/07/01/2020-internship-test/

더 직관적인 알고리즘인 것 같다.

1. 조건이 만족될 때까지 right++ (빈도수 +1)
2. 조건이 만족되면 left++ (빈도수-1, 빈도수 0이 되면 Map에서 삭제)
3. right이 범위를 초과할 때까지 반복

function solution(gems) {
    const cnt = new Set(gems).size;
    var ans = [1, gems.length];

    var l = 0, r = 0;
    const hit = new Map();
    hit.set(gems[0], 1)

    while (r < gems.length) {
        if (hit.size === cnt) {
            if(ans[1] - ans[0] > r - l)
                ans = [l + 1, r + 1]

            hit.set(gems[l], hit.get(gems[l]) - 1);
            if (hit.get(gems[l]) === 0) 
                hit.delete(gems[l])

            l++;
        }
        else {
            r++;
            const right = hit.get(gems[r]);
            hit.set(gems[r], right ? right + 1 : 1);
        }
    }
    return ans;
}