프로그래머스. 보석쇼핑

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

코딩테스트 연습 - 보석 쇼핑

 

gems 배열의 크기가 최대 10만이기 때문에 for문을 중첩해서 돌려서는 풀수없다.

 

1. gems 배열을 탐색하면서 map 자료구조에 <보석, 갯수> 형태로 각 보석의 갯수를 카운팅하고, 보석 종류의 갯수를 기억한다. (map의 size가 곧 보석의 종류이다)

 

2. 또다시 gems 배열을 돌면서 map에 <보석,갯수> 형태로 카운팅하다가 map의 size가 보석종류의 갯수와 같아지면 모든 종류의 보석들을 적어도 하나씩은 고른것이므로 그 지점이 end 지점이다.

 

3. 다시 gems 배열을 돌면서 map에서 보석을 하나씩 빼면서 start를 증가시킨다. 

 

4. 보석을 하나 뺏을때 해당 보석의 갯수가 0개가 됐다면,  end 지점 이후에 해당 보석이 존재하는지 확인하고, 존재한다면 end를 그 지점      으로 옮긴다.

 

5. end가 gems 배열의 끝에 도달할때까지 반복하면서 end-start가 최소인 값을 기록한다. 

 

 

---

2022.05.05

 

map<string, int> map // 보석이름, 갯수 

start, end 지점 0 부터 시작.

end 인덱스를 1 증가 시키고 해당 보석 갯수 증가.

start 지점부터 end 지점전까지, 새롭게 추가한 보석에 의해 제외해도 괜찮은 map에 갯수가 2이상있는 보석 탐색하고 제거.