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

Two Pointer 알고리즘 연습용으로 선택한 문제!
Set() 을 사용해 아래와 같이 간단하게 풀었다.

function solution(gems) {
  let answer = [];

  let allSpecies = new Set(gems); // 모든 종류의 요소가 각각 1번만 담기는 set()
  let minArr = [];
  let minLength = gems.length;
  let s = 0;
  let e = 0;

  while (e < gems.length) {
    let items = new Set();
    for (let i = s; i <= e; i++) { // 반복문을 돌며 구간 내의 요소들로 하나의 set을 만든다.
      items.add(gems[i]);
    }
    if (items.size === allSpecies.size) {  // 이 새로 만든 set이 모든 종류의 요소가 담긴 set과 크기 같으면 통과
      if (e - s < minLength || (e - s === minLength && s < minLength[0])) {
        minLength = e - s;
        minArr = [s + 1, e + 1];
      }
    }
    if (allSpecies.size <= items.size) {
      s++;
    } else {
      e++;
    }
  }
  answer = minArr;
  return answer;
}

테스트 케이스를 모두 통과해서 문제 없다 생각했건만..

효율성이...!!!😭

대체 내 코드의 효율성에 뭐가 문제인 것인가, 이걸 찾아보고자 고민해보고 남의 코드도 살펴보니...!
Map 객체를 쓰면 min 비교가 필요 없었다..!

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

Map은 키와 값을 저장할 수 있는 객체인데, 이걸 사용하면 훨씬 더 효율적으로 풀 수 있다(아래 코드 참고)
내가 짠 코드의 경우 구간의 요소들 구하기 위해 1) end pointer을 while문에 집어넣고, 2) 구간을 도는 for 반복문을 사용해서 s나 e가 달라질때마다 반복문을 돌아야 했었는데,
아래의 코드는 맵을 써서 인덱스를 저장해둬서 조건을 충족하기 전까지는 r(==end pointer)을 계속 옮겨두고, 조건이 충족되면 그때 최소구간인지 여부를 따져 ans 배열에 넣고, 그 후 l( == start pointer)을 한 칸 앞으로 이동시킨다. 이때 옮기는 방식도 hit안의 r에 해당하는 값 을 delete로 없애버림으로써, 자동으로 두번째 인자가 r이 되도록 만든다.

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;
}

최종적으로 내가 수정한 알고리즘은 다음과 같다.

function solution(gems) {

  const count = new Set(gems).size; // 중복 없는 Set의 크기
  let answer = [1, gems.length]; // answer의 초기값은 1과 gems.length(0 + 1, 끝 인덱스 + 1)
  let start = 0,
    end = 0; // 시작 포인터(start), 끝 포인터(end)
  const temp = new Map(); // 구간 내의 모든 인자가 담길 temp Map 객체
  temp.set(gems[0], 1); // temp 맵 객체에 먼저 0번째 인자를 넣는다.

  while (end < gems.length) {
    // 끝 포인터가 인덱스 끝까지 가면 반복문 종료
    if (temp.size === count) {
      // start를 옮기는 조건 => 1) 모든 요소가 배열 안에 들어왔을 경우
      if (answer[1] - answer[0] > end - start) {
        // 2) 최소구간이 증명되면 answer에 넣는다.
        answer = [start + 1, end + 1];
      }
      temp.set(gems[start], temp.get(gems[start]) - 1); // start를 하나씩 옮기며 중복 요소를 하나씩 제거해서 마침내 중복이 없어진 요소(값이 1인)만 ans에 남게 된다.
      if (temp.get(gems[start]) === 0) {
        // 안에 요소의 값이 0개면 아예 해당 키를 없애자.
        temp.delete(gems[start]);
      }
      start++;
    } else {
      // start를 너무 옮겨 아예 요소 자체가 MAP에서 삭제되면 end를 옮기게 된다.(temp의 size가 count와 달라질테니)
      end++;
      let endValue = temp.get(gems[end]);
      temp.set(gems[end], endValue ? endValue + 1 : 1);
    }
  }
  return answer;
}

결론: Map(), Set() 객체를 잘 쓰자 / 반복문을 최대한 쓰지 않고, 빈 배열도 최대한 쓰지 않아야 메모리와 시간 효율성 확보 가능하다!