[프로그래머스] 보석 쇼핑

문제

[프로그래머스] 보석 쇼핑

접근 방식

• 완전 탐색으로는 시간복잡도 O(n^2)여서 안된다
• 카카오 해설 -> 투포인터로 풀라고 한다..

카카오 문제 해설
1. 맵 자료구조에서 map[보석이름] = 빈도수로 정의한다.
2. 왼쪽 포인터 l과 오른쪽 포인터 r을 모두 1번 진열대에 위치시킨다.
3. 양 포인터 중, 둘 중 하나라도 진열대의 범위를 벗어나면 알고리즘을 종료한다.
4. 양 포인터가 가리키는 범위 안에 포함된 보석 종류의 개수를 세어 본다.(map의 사이즈를 체크)
5-1. 범위 안에 보석 종류가 전체 보석 종류와 일치하면 더 좋은 답인지 체크한 후 l을 증가시킨다. 그리고 2로 간다.
5-2. 범위 안에 보석 종류가 전체 보석 종류보다 작다면 r을 증가시킨다. 그리고 3으로 간다.

즉, 포인터 l과 r을 이용하여 보석의 종류가 모자라면 r을 증가시키고,(보석 더함) 보석의 종류가 충분하면 l를 증가시키는(보석 뺌) 과정을 반복하며 정답을 갱신시킨다.
이때 l을 증가시키기 이전 map 자료구조에서 l번 진열대에 있던 보석의 빈도수를 감소시켜주어야 하며 특히 빈도수가 1에서 0이 될 때에는 map에서 완전히 제거해야 한다. r을 증가시킬 때는 map 자료구조에서 증가된 r번 진열대에 있는 보석의 빈도수를 증가시켜준다.

https://tech.kakao.com/2020/07/01/2020-internship-test/

정답 코드

def solution(gems):
    n = len(gems) 
    answer = [0, n-1]
    dic = {gems[0]:1}
    kind = len(set(gems)) # 보석 종류
    left, right = 0, 0 # 투포인터
    
    while left < n and right < n:
        if len(dic) < kind:
            right += 1
            
            if right == n:
                break
            
            if gems[right] not in dic:
                dic[gems[right]] = 1
            else:
                dic[gems[right]] += 1
                
        else:
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
            else:
                dic[gems[left]] -= 1
                if dic[gems[left]] == 0:
                    del dic[gems[left]]
                left += 1

    return [answer[0]+1, answer[1]+1]