프로그래머스 (보석 쇼핑) using python

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

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

이 문제 설명의 키워드는 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매와 같다.

결국  보석 종류가 다 포함된 가장 짧은 구간을 찾으면 된다.

입출력 설명

나의 풀이 ( 효율성 3개 실패) 

def solution(gems):
    # 중복이 제거된 보물 리스트
    bomul = list(set(gems))
    # 보물 딕셔너리
    bomul_dict = {}
    # 최소값 찾기
    min_value = 1000000
    # 정답 list
    answer = [1, 100000]
    # 딕셔너리에 key값을 보물 name value 값을 0으로 넣기
    for b in bomul:
        bomul_dict[b] = 0
    # 실제로 보물을 검색해가면서 dictionary 값을넣기
    for i in range(len(gems)):
        bomul_dict[gems[i]] = i+1
        # 여기서 빅오가 n을 넘어서 안되는거 같다.
        mi = min(bomul_dict.values())
        # 모든 최솟값이 1 이상일 경우에만 다 들어가 있으므로 이때부터 계산
        if mi:
            # 최솟값 비교해서 더작으면 최솟값에 넣기
            if (i+1) - mi < min_value:
                answer = [mi, i+1]
                min_value = i + 1 - mi

    return answer

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

다른 풀이 참조(투 포인터)

설명의 주석을 보면 참고 가능함.

def solution(gems):
    answer = [0, len(gems)] # 정답 넣기
    # 보물의 총 갯수
    n = len(gems)  
    # 보물의 종류수
    len_bomul = len(set(gems))   
    # 왼쪽은 0 오른쪽은 -1으로 시작 이유는 왼쪽은 idx가 0부터이므로인데 오른쪽은 바로 1을 더해주기 때문에 첫값을 생각해주기 위해 
    left, right = 0, -1 
    bomul_dict = {} # 딕셔너리
    
    # 투포인터(왼쪽이 n과 똑같을 때 while문 종료)
    while left < n:
        # 보물의 길이와 현재 보물 딕셔너리 값의 길이가 같은 경우는 투포인터 범위안에 보석이 다 들어 있음을 의미한다
        if len_bomul == len(bomul_dict):
            # 정답과의 길이 비교해서 더 작을 경우 정답 갱신해주기
            if right - left < answer[1] - answer[0]:
                answer[1], answer[0] = right, left
            # 범위 안이 딱 맞으므로 이제 왼쪽을 한칸씩 당겨주면서 포함 되지 않은 보석들을 제거해준다.
            bomul_dict[gems[left]] -= 1
            if not bomul_dict[gems[left]]:
                del bomul_dict[gems[left]]
            left += 1
        else:
            # 딕셔너리안에 보석이 다 없으므로 오른쪽을 한칸씩 늘려준다
            right += 1
            # 총 보물의 수와 현재 오른쪽의 있는 수가 같을 경우는 idx를 벗어난 경우이므로 break
            if right == len(gems):
                break
            # get을 이용해서 보물딕셔너리안에 그 보석이 있을 경우 그 value에서 1을 더하고 없을 경우에는 새로만들어 value는 0에서 1을 더한다,
            bomul_dict[gems[right]] = bomul_dict.get(gems[right], 0) + 1
    # 정답의 경우에는 원래 1부터 시작인데 0부터 시작했으므로 1씩 더해준다
    return [answer[0]+1, answer[1]+1]