[ programmers ] 보석 쇼핑 67258번 ( python )

문제

프로그래머스 67258번 보석 쇼핑 풀이 ( 파이썬 )

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

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

 

풀이

일단 풀이를 위해 투포인터와 dict을 이용했다. len을 이용해 len(dict)을 사용하면 키의 개수가 나오는 데 이걸 이용해서 투 포인터를 사용한다.

초기에는 dic[gems[0]] = 1으로 현재 DIA만 dic에 들어가 있다. 그래서 len(dic)은 1이 되므로 총 들어가 있는 보석이  4개(size)이므로

 

elif len(dic) < size:
    if right >= len(gems):
    	break
    dic[gems[right]] = dic.get(gems[right], 0) + 1
    right += 1

부분에 들어가게 된다. right가 1이므로 RUBY를 추가 시키고 right를 1 증가 시켜준다.

그럼 dic에는 RUBY까지 들어가서 len(dic)이 2가 된다. 만약 이렇게 증가하다가 len(dic)이 size 수인 4에 도달한다면

반대로 left를 증가시킬 것이다. 예시를 보면

right가 증가하다가 SHPPHIRE를 포함하면서 len(dic)이 size인 4와 같은 값을 가지게 되고 이제는 left 값이 증가하다가 

이 값이 정답으로 갖게 될 것이다.

 

마지막에 값을 넣을 때 (right - left, left, right)값들을 넣고 sort하는 이유는 길이가 가장 짧아야하고 가장 작은 인덱스를 가져야 하기 때문이다.

 

def solution(gems):
    answer = []
    get_set = set(gems)
    
    dic = dict()
    dic[gems[0]] = 1
    size = len(get_set)
    
    left = 0
    right = 1

    while left < right:
        if len(dic) == size:
            answer.append((right - left, left, right))

            dic[gems[left]] -= 1

            if dic[gems[left]] == 0:
                del dic[gems[left]]
            left += 1

        elif len(dic) < size:
            if right >= len(gems):
                break
            dic[gems[right]] = dic.get(gems[right], 0) + 1
            right += 1
        else:
            
            if dic[gems[left]] > 0:
                dic[gems[left]] -= 1
            else:
                del dic[gems[left]]
            left += 1
    
    answer.sort()
    
    ans = [answer[0][1] + 1, answer[0][2]]
    
    return ans