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

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

이 문제.. 효율성에서 엄청 애를 썼다.
4번에 큰 수정 끝에 성공했다.(의미있는 수정만 4번이지 제출은 수도 없이 한것 같다..) 하지만 그 4번의 성과가 헛수고는 아니고 배울점이 많았다. 마무리에 각 시도를 통해서 배운점을 작성할 예정이다.

일단 문제는 모든 요소 종류를 포함하는 가장 짧은 인덱스 범위를 구하는 문제다.

로직자체는 간단하다!

해결방법

• 초기 answer은 가장 큰 값인 [0,100001]을 넣고 시작했다.

1. gemLen: Set을 이용해 주어진 보석이 총 몇 종류 인지 파악.
2. gemMap: Map에 key:보석이름, value: 그 보석의 인덱스 를 저장할 예정
3. gems(보석배열)을 순회하며 gemMap에 있을시 그 기존 값을 삭제하고 새로운 인덱스로 업데이트 해준다. (이 과정이 내가 제일 헤매이던 부분이다.)
   • 그냥 덮어씌우지? 라고 생각할 수 있다. 나도 처음에는 그랬다.
   • Map은 순서를 유지해주는 특성을 이용하기 위해 삭제를 하고 넣어준다. 즉, 이렇게 하게되면 Map.values()의 이터러블의 맨 첫번째 next()의 value가 가장 작은 값 (제일 초반에 들어온 값)이 된다.
4. Map의 크기와 gemLen (보석이 종류)가 같아졌을 때 answer에 저장한 값과 지금 업데이트된 tmpIdx 값을 비교해준다.
   • tmpIdx의 최솟값 : gemMap.values().next().value (아까 삭제하고 추가한 이유가 여기에 있다.
   • 최댓값: i+1
5. tmpIdx의 길이가 더 짧다면 answer=tmpIdx로 answer 업데이트
6. 출력

code

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

  let gemLen = new Set(gems).size;
  let gemMap = new Map();

  for (let i = 0; i < gems.length; i++) {
    gemMap.delete(gems[i]); //Map에 있으면 삭제된다.
    gemMap.set(gems[i], i + 1); //새로운 값이 됐다.

    if (gemMap.size === gemLen) {
      const tmpIdx = [gemMap.values().next().value, i + 1];
      const answerLen = answer[1] - answer[0];
      const mapLen = tmpIdx[1] - tmpIdx[0];
      if (answerLen > mapLen) {
        answer = tmpIdx;
      }
    }
  }
  return answer;
}

마무리

여러번의 시도 끝에 결국 해결했다. 깃허브_보석쇼핑 여기에 작성한 코드와 수정하면서 각 채점결과를 작성해놨다. 이를 토대로 시간효율성에 관련해 몇가지 배울 수 있었다.

• Map객체를 시도해보고 Object로 바꿔서 해봤지만 Map이 훨씬 빨랐다.

이 문제에서는 Map이나 Object의 길이를 구해야 되는 부분이 있어서 그런지 Map이 훨씬 시간이 빨랐다.

• 이터러블 객체를 Math.min 과 같은 Math함수와 전개연산자를 이용해서 사용하는 것보다는 for of 구문으로 하나씩 비교해서 구하는게 더 시간이 빨랐다.

지금 생각해보면 전개연산자에서 한번 시간을 쓰고 Math함수에서도 시간을 쓰기 때문에 그럴까..? Math함수가 어떻게 구현됐는지 모르기 때문에 정확하게는 모르지만 for of구문으로 비교해주는게 훨씬 빨랐다.
이렇게까지 했을 때 마지막 효율성 15번만 막혔었는데 위의 정답 풀이로하니 비교도 할 수 없을 만큼 큰 시간차가 있었다. Map을 매번 순회해야되는데 오래걸리는게 당연하다.

예전에 한번 시도했었던 문제였는데 실패를 하고 다시 도전한 문제이다.

다른 분들의 풀이에 많은 분들이 투포인터라는 방법을 이용하셨다. 투포인터라는 것도 알아보고 그방법으로도 한번 해결해 볼 예정이다.