[투 포인터] 보석 쇼핑 (파이썬)

문제 설명

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

프로그래머스

문제 풀이

• 투 포인터를 이용해서
• 모든 보석 종류를 수집하지 못했다면 end +1
• 모든 보석 종류를 수집해서 end까지의 최소 길이 구하기 위해 start+1
• 특정 보석의 갯수는 딕셔너리를 이용해서 체크 
• 모든 보석 종류를 수집했는지는 r이라는 변수를 두고 수집 할 보석 갯수 nn 가 비교해서 알아냄
• r==nn 이면 모든 보석을 수집한 것이므로 최소 길이를 구하기 위해 start를 +1 씩 해주면서 체크
• 이 때 start가 거쳐간 것들의 보석 갯수는 -1 을 해주다가 특정 보석의 갯수가 0이 된다면 그곳이 최소 길이의 첫 시작이 된다.
• 위의 과정이 끝났다고 결과값이 나오는 것이 아니므로 이 후 탐방을 계속 해주면서 체크

소스 코드

# gems len 100,000 이하
def solution(gems):
    answer = [0,len(gems)]
    result = len(gems)
    w = list(set(gems))	# 보석 종류 알기 위해 집합
    cnt = dict()		# 탐방 시 보석 갯수 체크
    for i,ddd in enumerate(w):
        cnt[ddd]=0
    n = len(gems)	# 탐방 할 보석 전체 길이
    nn = len(w)		# 주어진 보석 갯수
    if(nn==1):		# 보석 한 종류면 그냥 끝
        return [1,1]
    
    start,end =0,0		#투 포인터
    cnt[gems[end]]=1	
    r=1					#보석 다 모았는지 체크 용도
    
    while(start<n and end<n):
        if(r==nn):
            if (end-start<result):
                answer=[start,end]
                result=end-start
            else:
                cnt[gems[start]]-=1
                if cnt[gems[start]]==0:
                    r-=1
                start+=1
        else:
            end+=1
            if(end==n):
                break
            cnt[gems[end]]+=1
            if(cnt[gems[end]])==1:
                r+=1
    
    return [answer[0]+1,answer[1]+1]

print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))

ㅡ