프로그래머스 LEVEL 3(보석 쇼핑)

사용 언어 : javascript
해결 날짜 : 2022-10-17
해결 방법 :
- 처음에 start부터 end 인덱스 까지 slice()를 활용하여 자른 배열을 비교하였으나, 효율성 문제에 막힘
- Map() 자료구조를 활용하여 map의 size가 kind보다 작은 경우, end 증가 및 map에서 end 인덱스에 해당하는 값 1 증가
- 같은 경우, 정답 배열보다 구간이 짧다면 업데이트, start 증가, map에서 start 인덱스에 해당하는 값 1 감소
  - 이 때, 감소시킨 값이 0이 된다면 map에서 제거 (why? size 비교를 위해)
회고 :
- Array.splice()나 Array.slice()도 Map().size와 똑같은 O(n)이지만, Map() 활용 시 중복 제거된 length 만큼만 돌기 때문에 훨씬 빠름
- 효율성 테스트 통과하기 위해 Map() 자료구조를 활용하는 습관 들이기

코드

function solution(gems) {
    const kind = new Set(gems).size;
    let answer = [1, gems.length];
        
    let start = 0, end = 0;
    const map = new Map([[gems[0], 1]]);

    while (end < gems.length) {
        if (map.size < kind) {
            const last = map.get(gems[++end]);
            map.set(gems[end], last === undefined ? 1 : last + 1);
        } else {
            if (answer[1] - answer[0] > end - start) answer = [start + 1, end + 1];
            const current = gems[start++];
            map.set(current, map.get(current) - 1);
            if (!map.get(current)) map.delete(current);
        }
    }
        
    return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges