[2020 카카오 인턴십] 보석쇼핑 JavaScript

문제

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

풀이

해당 문제는 인턴 시험 칠 때 못 풀었던 문제다. 투 포인터라는 개념에 대해 몰랐엇다. 시험을 치고 나서 다른 분들과 얘기해보다가 투포인터라는 것에 대해 알게 되었다.

예를 들어
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
이렇게 주어졌을 때 Set을 통해 전체 보석들이 다 들어있을 때의 길이를 알 수 있다.
현재는 ["DIA", "RUBY", "EMERALD", "SAPPHIRE"]가 들어있는 4가 모두가 들어있을 때의 길이이다.

그러면 이것을 어떻게 구하느냐가 문제다.
처음 시작점과 끝점을 0으로 잡는다. 그러면 현재는 "DIA" 하나가 있다. 이제 보석들을 포함 할 때까지 끝점을 1씩 증가시킨다. 그러면 끝점은 "SAPPHIRE" 까지 가게 된다. 그러면 이제 모든 보석을 포함하고 있으니 start를 1씩 증가시키며 조건을 만족하는지 확인한다.

첫번째 "DIA"를 빼더라도 뒤에 "DIA"가 있기 때문에 상관없다. 그 다음 "RUBY"를 빼더라도 그 뒤에 "RUBY"가 있기 때문에 상관없다. 그 다음 "RUBY"는 빼면 조건이 성립하지 않는다.
그러면 "RUBY"가 없어 조건을 다시 성립하게 하기 위해 end를 증가시킨다. 증가를 끝까지 시켜도 "RUBY"가 없기 때문에 끝이난다.

그럼 앞에서 가장 짧았을 때의 구간을 답으로 출력하면 된다.

코드

function solution(gems) {
  const result = new Set(gems);
  const resultSize = result.size;
  const gemsLength = gems.length;
  
  const nowGems = new Map(); // 보석들을 담아둘 Map
  nowGems.set(gems[0], 1); // 처음 gems을 넣어둔다.
  
  let start = 0;
  let end = 0;
  let answer = [0, gemsLength - 1];//제일 길 때의 답.
  
  while (end < gemsLength && start <= end) {
    // Map은 size를 통해 key의 개수를 알 수 있다. 같을 경우 모든 보석들이 있는 것이다.
    // 길이를 비교해서 answer를 정하고 같을 경우 start 지점이 빠른걸로 answer를 정한다.
    if (resultSize === nowGems.size) {
      if (end - start < answer[1] - answer[0]) {
        answer = [start, end];
      }
      if (end - start === answer[1] - answer[0]) {
        if (start < answer[0]) {
          answer = [start, end];
        }
      }
      // 만약 해당 보석의 개수가 2개 이상이면 -1을 해주고 1개였을 경우 빼야 하므로 delete 시켜준다.
      if (nowGems.get(gems[start]) > 1) {
        nowGems.set(gems[start], nowGems.get(gems[start]) - 1);
      } else {
        nowGems.delete(gems[start]);
      }
      start += 1;
    } 
    // 만약 end 지점의 보석이 있을 경우 1로, 없을 경우 원래 값에서 + 1을 해준다.
    else {
      end += 1;
      nowGems.set(gems[end], 1 + (nowGems.get(gems[end]) || 0));
    }
  }
  
  return [answer[0] + 1, answer[1] + 1];
}