알고리즘 정복기 해시 - (2)

프로그래머스 문제를 풀며 지금은 2~3 level수준의 문제를 하루에 최소 1문제씩은 풀어나가고 있다. 사실 2~3문제를 목표로 하고있는데 오늘의 문제는 하루를 모두 쏟아서 풀었다. 처음 아래의 문제를 접할 땐 투포인터로 접근을 계속해서 시도를 했다.. 결과는 정확도 테스트는 모두 통과했지만 효율성 테스트 4개의 케이스에서 실패했고 점수는 83점이었다.. 계속 고민을 해봤지만 도저히 떠오르지 않아. 구글링을 해 해답을 찾아보았다. 코딩테스트를 하다보면 수학문제랑 매우 비슷함을 느낀다. 학창시절 수학문제가 막혀 결국 해설을 보면 아! 이거구나 싶지만 개운함은 없다. 내가 끝까지 풀고 해답을 봤을 때 만큼 시원하지 않다. 코딩테스트도 마찬가지인거 같다. 구글링을 최대한 안해보려했지만 너무 궁금하고 인내하지 못해 해답을 봐버린 것이다. 보고나니 아 이런방법도 있구나 싶었다. 필자가 알아본 해결방법은 해시알고리즘으로 해결한 해답이었다.
아래에 문제를 첨부하겠다.

보석쇼핑 (kakao level3) ❓

문제 링크

설명을 하자면 다음과 같다. 욕심쟁이 어피치는 보석을 싹쓸이해가는 싹쓸이꾼이다. 근데 양심은 있다. 종류별로 최소 한가지를 가질 수 있는 최소한으로 싹쓸이해간다. 만약 A,B,C,D의 4가지 보석이 있다면 최소 1개씩 갖는 최소한의 길이만 싹쓸이해간다.

[A, B, D, A, B, C ,D]

위와 같은 배열(보석진열장)에서 모든 보석을 갖는 배열의 시작과 끝을 따져보면
[0,5] 도 가능하고 [3,6]도 가능하다. 그렇다면 원하는 정답은 [3,6]이 될 것이다. 왜? 배열의 start와 end의 차가 가장 적지 않은가!

생각하는 건 꽤 쉬운데 이를 코드로 변환하는 작업은 쉽지 않은 거 같다.

다양하게 시도를 해보았다. 하나씩 코드를 살펴보자
일단, input의 100,000이기 때문에 시간 복잡도를 따졌을 때
N이나 logn의 시간복잡도를 갖는 코드(알고리즘)이 필요했다.

첫번 째 시도 ❓

function solution(gems) {
  const gemsList = [...new Set([...gems])];
  const stack = [];
  let gemsIndex = [];
  if (gemsList.length === 1) {
    return [1, 1];
  }
  // 보석이 한가지만있는경우

  for (let i = 0; i < gems.length; i++) {
    if (!stack.includes(gems[i])) {
      stack.push(gems[i]);
      gemsIndex[gemsList.indexOf(gems[i])] = i;
      // gemsIndex에 gemsList에서 가장 최신의 index정보를 가져옴
    } else if (stack.includes(gems[i])) {
      gemsIndex[gemsList.indexOf(gems[i])] = i;
    }

    if (gemsIndex.length === gemsList.length) {
      //그때의 i를 배열에서 삭제
      gemsIndex.splice(i, 1);
    }
  }

  return [min, max];
}

위 코드는 한번의 반복문과 stack을 이용해서 해결해보려했는데 이는 정확성 테스트도 통과하지 못했다. 왜 그럴까? 위 논리에 따르면

[A, B, D, A, B, C ,D]에서 ABDABC가 답으로 나온다.

그냥 처음으로 모든 ABCD가 나왔을 때를 return 해버리니 그 뒤에 더 짧은 경우가 있을 수 있음에도 이는 무시되고 return 되어버렸다.

다시보니 그럼에도 잘한점은 가장 최신의 index 정보들을 가져왔다는 점이다.
ABDA 에서 A의 index 0 을 새롭게 3으로 저장해 나간 점은 위 정답 코드와 비슷한 로직을 따른다.

두 번째 시도 ❓

function solution(gems) {
  const gemsList = [...new Set([...gems])];
  const gemsIndex = Array.from({ length: gemsList.length }, () => -1);
  let answer = [];
  for (let i = 0; i < gems.length; i++) {
    const gemsListIndex = gemsList.indexOf(gems[i]);

    gemsIndex[gemsListIndex] = i;

    if (!gemsIndex.includes(-1)) {
      //같을 때
      const max = Math.max(...gemsIndex);
      const min = Math.min(...gemsIndex);
      const minIndex = gemsIndex.indexOf(min);
      answer.push([min, max]);
      gemsIndex[minIndex] = -1;
    }
  }

  answer = answer.sort((a, b) => a[1] - a[0] - (b[1] - b[0]));
  answer = answer[0];

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

위 로직은 모든 보석이 포함되는 처음의 case에 계속해서 업데이트를 해나가며 끝까지 그 index를 answer에 push 했다. 즉, gemsIndex를 이용해 arr의 모든 원소에 -1이 없는 순간(모든 종류의 보석을 갖는 순간)을 catch해서 answer에 push해 주고 sort하여 정답을 유추하였다.

위 코드의 결과는!! 정확성은 다 맞았지만 효율성에서 4개의 케이스에 실패하였다. 이보다 더 효율적으로 짜야한다. 또 효율성에 점수배점이 더 높은 것으로 봐서 이 문제는 시간복잡도에 대한 신경을 굉장히 많이 써야하는 거 같았다.

세 번째 시도 ❓

function solution(gems) {
  const gemsList = [...new Set([...gems])];
  const answer = [];
  let gemsSaved = new Map();

  for (let i = 0; i < gems.length; i++) {
    gemsSaved.set(gems[i], i);
    //hash로 저장

    const gemsSavedArr = [...gemsSaved];
    if (gemsSavedArr.length === gemsList.length) {
      gemsSavedArr.sort((a, b) => a[1] - b[1]);
      const gemsSavedArrMax = gemsSavedArr[gemsSavedArr.length - 1][1];
      const gemsSavedArrMin = gemsSavedArr[0][1];
      answer.push([gemsSavedArrMin, gemsSavedArrMax]);

      const gemsSavedArrMinKey = gemsSavedArr[0][0];

      delete gemsSavedArrMinKey;
    }
  }

  answer.sort((a, b) => a[1] - a[0] - (b[1] - b[0]));

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

이번엔 해시를 사용해서 만들었다. 해시를 사용한 이유는 해시의 시간 복잡도는 O(1)이기 때문에 가장 빠르기 때문에 해시를 사용하면 효율성을 통과할 수 있지 않을 까 생각했다. 그런데 지금와서 보면 이렇게 접근하는게 맞았다.. 다만 hash에 대한 그리고 new Map에 대한 이해가 부족했던 거 같다.

위 코드는 Hash로 모든 보석을 구하는 경우 (length === gemsList.length)를 구해서 그때의 index를 또 구해 answer에 Push 하였다. hash로 접근 한 것은 좋았지만 이를 다루는 방법에서 많이 어색했다.

new Map의 size? new Map.size

이것은 그냥 하나의 메서드에 대한 설명은데 new Map을 만들면 객체의 형태로 자료구조가 생성이 된다. 그렇다면 만약 이 Object의 길이를 사용하고 싶으면 Spread Operator를 사용해서 [...] 배열로 변환한 뒤 그 length를 찾았었다. 근데 이러지 않아도 된다. new Map.size를 하면 그 Object의 길이를 알 수 있다..!

Spread Operator => 시간 복잡도 O(n^2)??

이럴수가! 이게 이렇게 오래 걸리는 것이었다니.. 반복문안에 spread operator를 사용하면 시간복잡도는 O(n^4)이 되는 것이다 ㄷ ㄷ!
가급적 문제를 잘 보고 Spread Operator의 사용을 고민해야겠다.

네 번째 시도 ❓

function solution(gems) {
  // hash로 먼저 만들고
  // 그 인덱스를 기준으로 start와 end를 지정해서 push, shift를 이용해
  // 해를 구하기
  const answer = [];
  const gemsArr = [...new Set(gems)];
  let gemsHash = new Map();
  // hash만듦
  for (let i = 0; i < gems.length; i++) {
    if ([...gemsHash].length === gemsArr.length) {
      break;
    }
    gemsHash.set(gems[i], i);
  }
  gemsHash = [...gemsHash].sort((a, b) => a[1] - b[1]);

  let start = gemsHash[0][1] + 1;
  let end = gemsHash[gemsHash.length - 1][1];
  let target = gemsHash[0][1];
  answer.push(start, end + 1);
  while (end < gems.length) {
    console.log(end, start, target);
    end = end + 1;
    if (gems[end] === target) {
      answer.push([start, end]);
      target = start;
      start = start + 1;
    }
  }

  return answer;
}

위에선 먼저 Hash로 모든 보석을 갖게되는 처음 배열을 찾아낸 후 그리고 투포인터를 사용해서 문제를 푸려고 했다.. 이렇게 풀 수 있을 거 같은데.. 아직도 방법을 잘 모르겠다. 아니 방법을 구현하기가 힘들다.. 투포인터에 대한 이해가 아직 부족한거같다.

마지막 시도 ❓(구글링 함..😢)

function solution(gems) {
  const gemsKindNum = [...new Set(gems)].length;
  const gemsList = new Map();
  const answer = [];
  for (let i = 0; i < gems.length; i++) {
    gemsList.delete(gems[i]);
    // delete해주는 이유는 새로운 gems를 업데이트하기위해
    gemsList.set(gems[i], i);

    if (gemsList.size === gemsKindNum) {
      answer.push([gemsList.values().next().value + 1, i + 1]);
      // 첫번째 index의 value와 i 가 들어가야맞지
    }
  }

  answer.sort((a, b) => a[1] - a[0] - (b[1] - b[0]));

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

코드 길이부터 편안하다..

위에 보면 delete를 해주는 부분이 있다. 이를 먼저 설명해야할 거 같다.

자, 다음과 같은 보석 선반이 있다고 보자 [A,B,C,A,A,D,B,C]
Hash는 다음과 같이 담기는 것이다.

A=>0 B=>1 C=>2 여기에서?!
B=>1 C=>2 A=>3 이렇게!!! 이게 아무것도 아닌 거 같지만 이게뭐겠는가!!!
보석을 담는 처음부터 끝까지에서 처음이 무엇인지 마지막이 무엇인지를 알 수 있다는 것이다. B=>1이 시작이 되는 것이다!!! 계속 나아가보겠다.

B=>1 C=>2 A=>4 D=>5
자 여기서 모든 배열 꽉찼다 => map이 보석 종류 arr의 length와 같아졌다. 그럼 이제 여기서 B=>1을 push D=>5를 push할 수 있다. 어떻게??

이는 다음 챕터에서 설명하겠다.

이어서 자 그럼 B=>1 C=>2 A=>4 D=>5 이 상태에서 계속 나아가는 것이다.

C=>2 A=>4 D=>5 B=>6 또 4가지가 찼으니까 또 push

A=>4 D=>5 B=>6 C=>7 그럼 딱 봐도 이 배열이 가장 가깝게 밀도있게 붙어있음을 알 수 있다.

필자는 이게 가장 헷갈렸다 아니 그럼 보석이 연속이 아니라 떨어져있을 수도 있잖아?!?!

이게 무슨 말일까 ㅋㅋ

[A,B,C,C,A,C,A]

이런 경우에
A=>0 B=>1 C=>2 까진 좋다 그럼 ??
A=>0 B=>1 C=>3 연속되지 않자나? -1
B=>1 C=>3 A=>4 이것도 연속 되지 않잖아?
그런데 상관없다 왜냐면 1을 예시로 들면 그냥 A 부터 2번째 C까지 담는 것이지 앞에 있는 A가 사라지는 게 아니다. 손으로 담아가는 범위라 생각하면된다. 그럼 이제 이해가 된다.

map.values().next().value ❓

이를 이용해 첫 번째 value를 가져올 수 있다. 무슨말이냐면

위 values와 next는 메소드인데 map에 관련된 메소드이다.
map 메소드 정리 블로그

위 블로그에 아주 잘 정리되어 있는데 map.values는 map에 들어있는 value들을 가져올 수 있는 메소드이고 next는 한 번 쓸 때 마다 첫번 째 두 번째 세 번째 value를 가져올 수 있다.

위 코드에선 map.values().next().value니까 첫 번째 value를 가져온 것이다. values는 Map 객체에 저장된 모든 데이터의 value를 반환한다.

다시 문제로 돌아와서 ❗️

결과는

통과.. 사실 구글링을 통한 통과라 개운하지 않다. 하지만 이왕 해버린거 최대한 많이 배워야하지 않겠나!
이 문제를 풀며 생각한 점은 아 이렇게 논리적으로 생각할 수 있고 또, 창의적으로 생각할 수 있어야 level3문제를 풀 수 있는거구나. level2와 level3의 차이점은 시간복잡도와 관련이 있을 수 있겠다. 이 부분을 더 공부해야겠다. 라는 생각이 들었다.