[코딩테스트]프로그래머스 - 보석 쇼핑

[카카오 인턴] 보석 쇼핑

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한사항

• gems 배열의 크기는 1 이상 100,000 이하입니다.
• gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
• gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
• gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

입출력 예

gems									result
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
["AA", "AB", "AC", "AA", "AC"]						[1, 3]
["XYZ", "XYZ", "XYZ"]							[1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"]					[1, 5]

입출력 예에 대한 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

3종류의 보석(AA, AB, AC)을 모두 포함하는 가장 짧은 구간은 [1, 3], [2, 4]가 있습니다.
시작 진열대 번호가 더 작은 [1, 3]을 return 해주어야 합니다.

입출력 예 #3

1종류의 보석(XYZ)을 포함하는 가장 짧은 구간은 [1, 1], [2, 2], [3, 3]이 있습니다.
시작 진열대 번호가 가장 작은 [1, 1]을 return 해주어야 합니다.

입출력 예 #4

4종류의 보석(ZZZ, YYY, NNNN, BBB)을 모두 포함하는 구간은 [1, 5]가 유일합니다.
그러므로 [1, 5]를 return 해주어야 합니다.

해결한 코드

function solution(gems){
  var count = new Set(gems).size;
  // 보석 종류가 몇개인지 
  var gemMap = new Map()
  // 보석 종류 => 보석 자리를 저장하기 위한 맵
  var gemLength = []
  // 보석을 모두 포함하는 구간을 저장할 배열 
  gems.forEach((gem, i)=> {
    gemMap.delete(gem)
    gemMap.set(gem, i)
    if(gemMap.size === count){
      gemLength.push([gemMap.values().next().value + 1, i+1])
    }
  })
  
  gemLength.sort((a,b)=> {
    if(a[1]-a[0] === b[1]-b[0]){
      return a[1]-b[1]
    }
    return (a[1]-a[0])-(b[1]-b[0])
  })
  
  return gemLength[0]
}

알고리즘

1. 보석의 종류가 몇개인지 세어준다.

1-1. Set을 사용하여 중복을 제거한 원소의 size를 구한다.

2. 보석을 저장할 Map을 만든다.

2-1. Map = {'보석 이름' => '보석 자리'} 이런 식으로 구현하여 보석의 종류가 모두 포함된 구간을 구할 것이기 때문이다.

3. 이제 보석 배열(gems)을 돌면서 Map에 보석과 보석 자리를 저장한다.

3-1. 단, 새로 저장되는 보석과 같은 보석이 Map에 있으면, Map에 있던 기존 보석을 삭제한다.
3-2. 위의 과정을 예시로 들면 다음과 같다.

gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]
gemMap = {}

인 상태에서, 첫번째 원소 'DIA'부터 Map에 저장한다.

gemMap = {'DIA' => 0}

인덱스로 지정했기 때문에 보석 자리가 0으로 저장된다. 이는 나중에 +1 해줄 것이다.
두번째 원소 'RUBY'를 저장한다.

gemMap = {'DIA' => 0, 'RUBY' => 1}

세번째 원소 'RUBY'를 저장할 차례이다. 그런데 Map에 똑같은 'RUBY'가 있다.
Map에 있는 'RUBY'를 찾아 삭제한 후, 세번째 원소 'RUBY'를 저장한다.

gemMap = {'DIA' => 0, 'RUBY' => 2}

네번째 원소는 'DIA'이다. 위의 'RUBY'처럼 Map안에 있는 'DIA'를 삭제하고 네번째 원소 'DIA'를 저장한다.

gemMap = {'RUBY' => 2, 'DIA' => 3}

다섯번째 원소 'DIA'도 마찬가지다.

gemMap = {'RUBY' => 2, 'DIA' => 4}

여섯번째 원소 'EMERALD'는 Map에 없는 보석이다. 따라서 삭제 과정이 무시될 것이다.
'EMERALD'를 저장한다.

gemMap = {'RUBY' => 2, 'DIA' => 4, 'EMERALD' => 5}

일곱번째 원소 'SAPPHIRE'도 Map에 없는 보석이다. 삭제 과정이 무시되고, Map에 저장한다.

gemMap = {'RUBY' => 2, 'DIA' => 4, 'EMERALD' => 5, 'SAPPHIRE' => 6}

4. Map의 size가 보석 종류의 갯수와 일치하면, 해당 구간을 저장한다.

현재 gemMap의 size는 RUBY, DIA, EMERALD, SAPPHIRE로 보석 종류의 갯수와 일치한다.
따라서 gemMap의 values 중에서 첫번째 value값에 +1 해준 것과 현재 인덱스에 +1 해준 값을 저장하면 될 것이다.
gemMap의 values를 불러오면 다음과 같다.

gemMap.values() : [Map Iterator] { 2, 4, 5, 6 }

여기서 맨 첫번째 객체를 불러와야 하니까, next()를 한번만 사용한다.

gemMap.values().next() : { value: 2, done: false }

value: 2는 첫번째 객체의 value값이 2라는 의미이고, done: false는 gemMap 안에 현재 객체 뒤에도 또 객체들이 있다는 것을 의미한다.
(자세한 내용은 Map - JavaScript - MDN - Mozilla를 자세히 참고하는 것이 좋을 것 같다.)
이 객체의 value값이 구하고자 하는 구간의 첫번째 보석 자리의 인덱스이다. 따라서 value를 가져온다.

gemMap.values().next().value : 2

이 값은 인덱스이고, 실제 보석 자리는 인덱스+1이니 해당 값에 +1을 해준다.
마지막 구간은? 현재 Map에 넣은 보석 SAPPHIRE에 해당한 인덱스+1이다.
따라서 [gemMap.values().next().value + 1, i+1]의 형태로 저장한다.
📍 어? 어디에 저장해?
👉🏻 정답을 저장할 공간이 필요하다. 정답을 저장할 배열 gemLength를 만들고, 그곳에 push한다.

gemLength = [ [3, 7] ]

그럼 다시 보석을 gemMap에 넣는 과정으로 돌아간다. 마지막 여덟번째 원소 'DIA'를 gemMap에 넣는다.

gemMap = { 'RUBY' => 2, 'EMERALD' => 5, 'SAPPHIRE' => 6, 'DIA' => 7 }

이때에도 gemMap의 size는 보석 종류의 갯수와 같아진다.
위의 과정과 똑같은 절차로 gemLength에 저장하면,

gemLength = [ [3, 7], [3, 8] ]

이 된다.

5. 시작 진열대 번호가 더 작은 구간 or 더 짧은 구간을 반환한다.

gemLength의 원소는 보석을 구매할 구간이다.
만약 gemLength안에 구한 구간들의 크기가 모두 같다면, 시작 진열대 번호가 더 작은 것이 먼저 오도록 오름차순 정렬을 한다.
그렇지 않다면, 구간이 작은 것이 더 먼저 오도록 정렬한다.

gemLength = [ [3, 7], [3, 8] ]

에서 7-3=4, 8-3=5로 4<5이다. [3, 7]의 구간이 더 작으므로, gemLength를 정렬하면

gemLength = [ [3, 7], [3, 8] ]

이 된다.
이렇게 정렬된 배열의 첫번째 인덱스, gemLength[0]을 return해주면 된다.

내겐 정말 많은 시간이 소요되었던 문제..
좋은 수가 떠오르지 않아서 정말 많이 고민했다. 생각했던 방법들은 모두 시간초과가 났고... ㅠㅠ
마땅한 생각이 결국 떠오르지 않아 다른 사람의 풀이를 봤는데, 이 풀이가 가장 잘 이해되었고, 비교적 가장 간단하게 풀었다고 생각했다.
어떻게 이런 생각을 하지... 정말 대단하다.
이렇게 사고할 수 있을 때까지 열심히 하자 !!