[Level 3] 보석 쇼핑

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

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

---

접근

기본적으로 투 포인터 알고리즘을 적용하였다. left와 right가 처음에 0번째 인덱스를 가리킨다. 이제 right를 증가시키면서 해당되는 보석을 table에 추가한다. 만약 table의 길이가 보석의 종류와 같을 때는 최소 길이를 찾는다. 

 

구현

- 먼저 set을 통해 보석 종류의 개수를 구한다.

- left와 right가 0번째 인덱스를 가리키면서 탐색을  시작한다.

- right가 증가하면서 table에 보석의 개수를 추가한다.

- 만약 table의 key의 개수가 보석의 종류와 같을 때는 지금까지의 범위 내에서 가장 짧은 길이를 찾는다.

- 만약 현재 left가 가리키는 곳의 보석의 개수가 2개 이상일 때는 1개를 감소하고 left를 증가한다.

- 그렇지 않고 현재 최소 길이보다 right - left가 짧을 때는 최소 길이를 갱신하도록 한다.

- 위의 상황이 모두 아닐 때는 더 이상 탐색하지 않아도 되기 때문에 종료한다.

def solution(gems):
    answer = []
    size = len(gems) + 1
    set_size = len(set(gems))
    table = dict()
    left, right = 0, 0
    while right < len(gems):
        if gems[right] in table:
            table[gems[right]] += 1
        else:
            table[gems[right]] = 1
        
        right += 1
        
        if len(table) == set_size:
            while left < right:
                if table[gems[left]] > 1:
                    table[gems[left]] -= 1
                    left += 1
                elif size > right - left:
                    size = right - left
                    answer = [left+1, right]
                    break
                else:
                    break
    return answer