[JS] 보석 쇼핑

문제

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

프로그래머스

 

이 문제는 원래는 투포인터 알고리즘을 이용해 풀려했지만 도저히 방법이 생각나지 않아 참고를 좀 해봤다.

풀이 1

우선 Map 객체를 이용한 투포인터 접근법을 이용한 풀이다.

 

Map 객체는 중복처리가 가능하며 각 보석이 나온 최종 인덱스를 저장하며 사용한다.

map.delete(gems[i]);
map.set(gems[i], i);

 

delete를 하는 이유는 이미 있는 보석의 경우 같은 보석 중 나중에 나온 인덱스를 저장하기 위해 delete해주는 것이며, 처음 쇼핑하는 보석의 경우 동작하더라도 Map객체 내부에 없기 때문에 사실상 동작하지 않는다.

 

delete이후 set해주는 코드는 쇼핑하는 보석과 인덱스를 저장하기 위함이다.

 

코드 1

function solution1(gems) {
  const size = new Set(gems).size;
  const map = new Map();
  let answer = [1, gems.length];
    
  for (let i = 0; i < gems.length; i++) {
    map.delete(gems[i]);
    map.set(gems[i], i);
    if (size === map.size) {
      const range = [map.values().next().value + 1, i + 1];
      answer = answer[1] - answer[0] > range[1] - range[0] ? range : answer;
    }
  }   
  return answer;
}

 

풀이 2

이번 풀이는 일반적인 투포인터 알고리즘을 이용한 풀이다.

 

쇼핑한 보석 종류의 개수가 모든 보석의 종류의 수가 같은 경우 기존 값과 비교해 더 짧은 경우를 저장한다.

 

만약 쇼핑한 보석 종류의 개수가 적은 경우는 rp를 1씩 늘려가며 추가해준다.

 

코드 2

function solution2(gems) {
  const size = new Set(gems).size;
  const map = new Map();
  let answer = [1, gems.length];
  let lp = 0;
  let rp = 0;
    
  map.set(gems[0], 1);
    
  while (rp < gems.length) {
    if (size === map.size) {
      if (answer[1] - answer[0] > rp - lp) {
        answer = [lp + 1, rp + 1];
      }
            
      map.set(gems[lp], map.get(gems[lp]) - 1);
      if (map.get(gems[lp]) === 0) {
        map.delete(gems[lp]);
      }
      lp++;
    }
    else {
      rp++;
      map.set(gems[rp], map.has(gems[rp]) ? map.get(gems[rp]) + 1 : 1);
    }
  }
  return answer;
}