시작하며💧

4시간 밖에 못 잔 상태로 오늘 참 여러모로 많은 일들을 겪고 나니, 머리가 아예 돌아가지를 않았어요😥

더군다나 문제도 꽤나 어려워서인지, 쉽사리 풀지를 못하겠더라구요.

그래서 그냥 코드도 보지 않고 객체로 풀었다는 어떤 글을 보고, 나도 그래야겠다!는 확신을 얻고 객체로 접근을 해보았답니다.

결국 많은 착오를 겪고, 답을 찾아 갔어요! 같이 스터디한 분들께 미리 못 풀어서 죄송할 뿐이네요 😂😂

그럼, 한 번 시작해볼까요!

본론💻

처음에는 다음과 같이 풀고 시간초과가 났어요.

const solution = gems => {
  let answer = [0, 0];
  let [ start, end ] = [ 1, 1 ];
  const arr = [null, ...gems];
  let allJewels = [...new Set(gems).keys()];
  let allJewelObj = {};
  for (let i = 0; i < allJewels.length; i += 1) {
    allJewelObj[allJewels[i]] = 0;
  }
  while (start <= gems.length) {
    while (Object.values(allJewelObj).includes(0) && end <= gems.length) {
      allJewelObj[arr[end]] += 1;
      end += 1;
    }
    if (!Object.values(allJewelObj).includes(0)) {
      if ((answer[1] - answer[0] > end - 1 - start) || !answer[0]) {
        answer = [ start, end - 1 ];
      }
    }
    allJewelObj[arr[start]] -= 1;
    start += 1;
  }
  return answer;
}

이유를 짐작해보자면, 투포인터 알고리즘 외에 사용된 includes라던가, values 등의 문제로 O(n)이 곱절로 늘어난 건 아닐까 싶었어요.

그래서 객체로 푸는 게 아닌가...? 싶어서 다른 글들을 찾아 보니 객체로도 풀 수 있는 것 같더라구요!

2번째 시도. map

따라서 일단 values를 줄여보자는 마음가짐으로 다시 map으로 도전했어요.

const solution = gems => {
  let answer = [-Infinity, Infinity];
  let [start, end] = [1, 1];
  const arr = [null, ...gems];  
  const obj = new Map();
  const set = [... new Set(gems)];
  for (let i = 0; i < set.length; i += 1) {
    obj.set(set[i], 0);
  }
  while (start <= gems.length) {
    while ([...obj.values()].includes(0) && end <= gems.length) {
      const now = obj.get(arr[end]);
      obj.set(arr[end], !now ? 1 : now + 1)
      end += 1;
    }
    if (![...obj.values()].includes(0) && answer[1] - answer[0] > end - 1 - start) {
      answer = [ start, end - 1]
    }
    const now = obj.get(arr[start]);
    obj.set(arr[start], now - 1);
    start += 1;
  }
  return answer;
}

이번에는 맞겠지? 싶었는데 역시 시간초과가 나왔어오...😂😂
원인을 고민해봤는데요. 아무래도 includes가 역시 O(n)이라, O(n2)을 뚫지 못하는 듯 했어요.

그래서, includes를 쓰지 않고 풀 수 있는 방법이 뭘까? 고민을 시작했답니다.

세번째 시도, 틀리다.

세 번째로 시도를 해봤어요. 이번에는 map 객체에서 삭제하는 식으로 업데이트를 하면서, 최대값을 체크하는 거죠.

const solution = gems => {
  let answer = [-Infinity, Infinity]
  const maxCnt = [...new Set(gems)].length;
  const nowJewels = new Map();
  let [ start, end ] = [ 0, 0 ];
  
  while (start < gems.length) {
    while (maxCnt > nowJewels.size && end < gems.length) {
      nowJewels.set(gems[end], nowJewels.has(gems[end]) ? nowJewels.get(gems[end]) + 1 : 1);
      end += 1;
    }
    if (maxCnt === nowJewels.size && (answer[1] - answer[0] > end - start )) {
      answer = [ start + 1, end ];
    }
    const now = nowJewels.get(gems[start]);
    if (now === 1) nowJewels.delete(gems[start]);
    else nowJewels.set(gems[start], now - 1);
    start += 1;
  }

  return answer
}

그래서 테스트 케이스를 돌렸더니 맞아서, 아! 이제 쉬어야겠다 싶었는데

반이 틀리네오! 😂😂

또 원인을 고민해야 했죠.
그 결과 답은, 뒤쪽에서 더욱 최적의 답안이 있을 경우입니다!
결국 maxCnt가 더 클 때만 end가 올라가기 때문에, 결과적으로 제대로 동작하지 않는 것이죠.

따라서 다음이 반례입니다.

const gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA", "RUBY", "DIA", "EMERALD", "SAPPHIRE"]

따라서 저는... 미리 크기를 정하지 않고도 풀 수 있는 방법을 고민해야 했죠.

4번째 시도, 맞다 👊

결국 제가 원래 알던 것과 달리, while문을 2개 쓰기로 했어요.

제 생각은 다음과 같았습니다.

결국에는 right도 갈 수 있는 데까지 간다면, left도 갈 수 있는 데까지 가고, 이 둘을 answer과 비교한 후에, start를 하나 더해주면 되잖아?

결과적으로 이 역시 n크기의 반복문에서 한 번으로 끝낼 수 있기 때문에 O(n)을 만족할 수 있는 것이죠!

const solution = gems => {
  let answer = [-Infinity, Infinity]
  const maxCnt = [...new Set(gems)].length;
  const nowJewels = new Map();
  let [ start, end ] = [ 0, 0 ];
  
  while (start < gems.length) {
    while (maxCnt > nowJewels.size && end < gems.length) {
      nowJewels.set(gems[end], nowJewels.has(gems[end]) ? nowJewels.get(gems[end]) + 1 : 1);
      end += 1;
    }
    while (start < gems.length && nowJewels.get(gems[start]) !== 1) {
      nowJewels.set(gems[start], nowJewels.get(gems[start]) - 1);
      start += 1;
    }
    if (maxCnt === nowJewels.size && (answer[1] - answer[0] > end - start )) {
      answer = [ start, end ];
    }
    nowJewels.delete(gems[start])
    start += 1;
  }

  return [ answer[0] + 1, answer[1] ]
}

결과는?!

결국 고생하면서 맞추긴 했네요...!

마치며 😂

사실 오늘은 멘탈이 너무 안 좋아서, 풀 상황이 아니긴 했어요.
그렇지만 결국 이 역시 제 관리가 미흡하기 때문이었고, 온전히 제 변명인 거라, 앞으로 좀 더 침착하고, 의연한 사고를 가지려 노력해야겠다고 생각했습니다!

결국 사람이 힘들어도, 끝까지 노력하며 움직이며 남긴 발자취가 분명, 저를 어딘가로 이끌어줄 거라는 막연한 희망을 가지고 있어요.

다들 오늘도 고생 많았어요. 나 자신도 수고했다! 이상!!