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

 

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

---

투 포인터로 해결할 수 있는 문제입니다.

 

핵심은 N제한이 10만이므로 선형 탐색 한 번으로 탐색을 끝내야 한다는 점입니다.

 

문제를 해결하는 아이디어는 다음과 같습니다.

 

1. left, right를 선언해 현재 내가 구매할 보석의 하한 위치, 상한 위치 저장

 

2. 매 루프를 돌면서 right++ 을 통해 새로운 보석을 탐색합니다.

 

3-1. gems[right]가 현재 내가 가지고 있지 않은 보석이라면 내가 가지고 있는 보석 리스트에 추가합니다.

 

3-2. gems[right]가 현재 내가 가지고 있는 보석이라면,

 

3-2-1. 내가 구매할 보석 리스트 중 gems[left] 보석이 2개 이상이면 left++ 를 해줍니다.

 

무슨 말이냐면, 현재 내가 가지고 있는 left ~ right 사이에 있는 보석 중에 gems[left] 종류인 보석이

 

2개이상이라면, 맨 왼쪽(하한)에 있는 gems[left]는 안 사도 됩니다. 중간에 또 있을테니까요.

 

그래서 이 때 left++를 해줍니다.

 

4. 이렇게 루프를 끝까지 돌면서 (내가 현재 가지고 있는 보석 종류 갯수 == 전체 보석 갯수) 일 때 마다

 

(right - left, left, right) 값을 저장해줍니다.

 

5. 튜플을 통해 정답 후보가 되는 (구간의 길이, 시작 좌표, 끝 좌표)를 모두 저장한 뒤

 

가장 구간이 짧고 시작 좌표가 작은 값을 리턴해주면 됩니다.

---

코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/kakao2020_03.cc