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

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

---

투포인터로 풀었다.

gems를 돌면서 보석 종류 수를 구한다.

보석의 개수를 저장하는 cnts map을 하나 만든다. key = 보석이름, value = 보석 수.

그리고 탐색하면서 만난 보석들의 종류를 저장하는 set을 하나만든다. (let, exists)

 

투포인터의 오른쪽 인덱스(right)를 0부터 1씩 증가시키며 left 인덱스를 갱신한다.

탐색중인 보석의 수를 cnts 맵에 1더해서 갱신시킨다.

exists set에 탐색한 보석을 추가한다.

정답가능한 배열의 크기를 최소화로 만들기 위해 left인덱스를 갱신한다.

만일 gems[left] 에 해당하는 보석의 개수(cnts 참고)가 1보다 크다면 한 개 삭제해도 되므로 left를 1 더하고 cnts value를 1감소시킨다. left인덱스가 right 인덱스와 같아지거나 left 보석이 1개가 존재할때까지 이를 반복한다.

만일 exists 수(이때까지 탐색한 보석의 수)가 총 보석의 수와 같아진다면 left ~ right 배열의 크기가 정답 배열의 크기보다 작은경우 정답을 갱신한다.

 

시간복잡도는 O(N). N = |gems|.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/programmers/2020%EC%B9%B4%EC%B9%B4%EC%98%A4%EC%9D%B8%ED%84%B4%EC%8B%AD/%EB%B3%B4%EC%84%9D%20%EC%87%BC%ED%95%91.cpp