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

문제 출처

프로그래머스 lev3 - 보석 쇼핑

나의 풀이

슬라이딩 윈도우로 탐색을 시도했다.
크기가 크므로 중첩for은 역시나 시간초과가 발생한다.

function solution(gems) {
  const target = [...new Set(gems)].length
  let len = gems.length
  let s = 0
  let answer = [0, len]

  while(s !== len){
    for(let i=s; i<len; i++){
      const curr = [...new Set(gems.slice(s, i+1))]
      const currLen = curr.length

      if(target === currLen){
        const [a, b] = [s+1, i+1]
        if((answer[1]-answer[0]) > (b-a)){
          answer[0]=a
          answer[1]=b
        }
      }
    }
    s++
  }
  return answer
}

투포인터로 풀려했으나 여전히 시간초과가 발생한다..

answer에 들어갈 두 값을 left와 right로 나눈다. 그리고 단일 반복문으로 right를 가능할 때까지 들어가고, 마찬가지로 left도 단일 반복문으로 가능할 때까지 left를 찾는 접근을 하려 했으나 제대로 구현을 못했다...

다른 풀이 1

map을 사용한 투 포인터 풀이
(처음부터 끝까지 탐색해야 하는 문제지만, 단순하게 전부 탐색하려면 O(n^2)이 된다. 이를 줄이려면 탐색이되, 시간을 O(n)으로 줄일 수 있는 투포인터를 떠올리면 좋다.)

Map.prototype.values()는 map의 각 요소에 대한 값을 포함하는 새로운 iterator 객체를 반환한다.

• key값을 요소로 반환 받고 싶으면 Map.prototype.keys()
• key,value 모두 반환 받고 싶으면 Map.prototype[Symbol.iterator]
• values, keys, [Symbol.iterator] 전부 값을 가진 객체에 접근할 때는 next() 메서드를 사용해 접근한다.

map()은 삽입 순서를 유지해준다.

이 값들은 next()를 통해 value가 들어 있는 객체에 접근할 수 있다. 그러므로 next().value로 값을 찾을 수 있다. 삽입 순서를 유지하므로 첫번쨰 next().value는 항상 첫번째 요소를 반환한다.

forEach()에서 현재 요소의 이전 정보를 삭제하고 다시 삽입하는 식으로 계속 앞단을 업데이트해준다.

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

console.log(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))
// console.log(solution(["AA", "AB", "AC", "AA", "AC"]))
// console.log(solution(["XYZ", "XYZ", "XYZ"]))
// console.log(solution(["ZZZ", "YYY", "NNNN", "YYY", "BBB"]))

참고로, 이터레이터는 next 메서드를 가지며, next()의 반환값은 value 프로퍼티와 done 프로퍼티를 가진 객체이어야 한다.

위 코드에서 gemMap.values()가 이터레이터 객체인데, 단순히 값을 저장하지 않고 next()를 반복하면 처음 시작값만 계속 되풀이한다.

console.log(gemMap.values().next())
console.log(gemMap.values().next())
console.log(gemMap.values().next())

위 코드를 보면 계속 같은 값만 로그로 찍힐 뿐, next() 메서드를 사용해도 다음 객체를 반환하지 않는다.

next() 메서드를 사용해서 다음 값으로 넘어가고 싶다면 아래 코드처럼 이터레이터 객체로 저장을 하고 나서 가져다 쓰는 접근으로 변경해야 한다.

const iterator = gemMap.values()

console.log(iterator.next())
console.log(iterator.next())
console.log(iterator.next())

다른 풀이 2

문제 해설
1. 맵 자료구조에서, ‘map[보석 이름] = 빈도수’로 정의를 합니다.
2. 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킵니다.
3. 양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료합니다.
4. 양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 봅니다.(map의 사이즈를 체크합니다)
5.

• 5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l를 증가시킵니다. 그리고 2로 갑니다.
• 5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r를 증가시킵니다. 그리고 3으로 갑니다.

즉, 왼쪽을 가리키는 포인터 l과 오른쪽을 가리키는 포인터 r을 이용하여 보석의 종류가 모자라면 r을 증가시키고, 보석의 종류가 충분하면 l을 증가시키는 과정을 반복하면서, 정답을 갱신시켜나갑니다. 이때 l을 증가시키기 이전, map자료구조에서 l번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 map에서 완전히 제거하여야 합니다. r을 증가시킬 때는 map자료구조에서 증가된 r번 진열대에 있는 보석의 빈도수를 증가시켜줍니다.

개수가 부족하면 right을 증가시키고
개수가 충족되면 left를 증가시켜서 최적의 답을 찾는다.
(left하나 증가시키면 그에 맞는 요소를 하나 지워줘야 하는데, 그걸 빈도수로 측정한다. 빈도수가 0이면 delete해준다.)

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

참고

JavaScript - 이터레이터(iterator)와 for/of 문
[JS] 프로그래머스 보석 쇼핑