[Python] 보석 쇼핑

def solution(gems):

    n = len(gems)
    gem_kinds = len(set(gems))
    dic = {gems[0]:1}
    l, r = 0, 0
    
    answer = [1, n]
    
    while n > l :
        if len(dic) != gem_kinds :
            r += 1
            if r >= n :
                break
            
            if gems[r] in dic :
                dic[gems[r]] += 1
            else :
                dic[gems[r]] = 1
                
        else :
            if r - l < answer[1] - answer[0]:
                answer = [l+1, r+1]
                
            if dic[gems[l]] != 1 :
                dic[gems[l]] -= 1
            else :
                del dic[gems[l]] 
                
            l += 1
                
    return answer

---

풀이

투 포인터 방식으로 풀어야 하는 문제 ! 

 

1) 처음 설정

    n = len(gems)
    gem_kinds = len(set(gems))
    dic = {gems[0]:1}
    l, r = 0, 0
    answer = [1, n]
    
    while n > l :

① gems의 길이를 n변수에 넣어준다. (gems의 길이보다 넘는걸 막기 위함)

② 보석의 종류를 set함수를 이용해 gem_kinds 에 넣어준다. 

③ 보석의 빈도수를 저장하기 위해 딕셔너리를 만들어준다. 첫번째 보석에서 시작이니, 빈도수가 이미 1이므로 gems[0] : 1 을 넣어준다.

④ 왼쪽, 오른쪽 인덱스를 0, 0으로 설정해준다.

⑤ 구매할 범위 설정해준다.

 

⑥ while문은 l이 n보다 작은 경우에만 돌도록 설정

 

2) if문

	if len(dic) != gem_kinds :
            r += 1
            if r >= n :
                break
            
            if gems[r] in dic :
                dic[gems[r]] += 1
            else :
                dic[gems[r]] = 1

만약  dic에 모든 종류의 보석이 다 들어오지 않았다면 ( ➡︎ dic 의 길이가 보석 종류의 길이와 다르다)

① 오른쪽으로 한칸 옮겨간다. (r + 1)

② - ➀만약 r이 gems의 끝이거나, gems를 넘어간다면 while문을 멈춘다.

③ - ➀ 만약 gems[r]이 dic에 있다면, 빈도수를 1 더해준다.

    - ➁ gems[r]이 dic에 없다면, 넣어주고 빈도수를 1로 지정해준다.

 

3) else문

	else :
            if r - l < answer[1] - answer[0]:
                answer = [l+1, r+1]
                
            if dic[gems[l]] != 1 :
                dic[gems[l]] -= 1
            else :
                del dic[gems[l]] 
                
            l += 1

dic에 모든 종류의 보석이 다 들어왔다면 l을 움직여볼 차례이다.

① r - l 이 현재 저장된 최소 범위(answer[1] - answer[0])보다 작을 경우, answer에 l+1, r+1을 저장해준다.

② 가장 왼쪽에 있는 보석을 구매 목록에서 제외해보자.

     - ➀ 만약 dic[gem[l]]의 빈도수가 1이 이상이라면 빈도수를 -1해준다.

     - ➁ 1개라면 dic에서 데이터를 지워준다.

            데이터를 제거하면 모든 종류의 보석을 구매할 수 없게 되므로, if문으로 들어가 r을 증가시킨다.

③ l + 1 해준다.