[프로그래머스] 보석 쇼핑 파이썬 풀이

[문제 링크]

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

[입출력 예]

gems	result
["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]	[3, 7]
["AA", "AB", "AC", "AA", "AC"]	[1, 3]
["XYZ", "XYZ", "XYZ"]	[1, 1]
["ZZZ", "YYY", "NNNN", "YYY", "BBB"]	[1, 5]

[1차시도 테스트케이스 4/4 제출 15.6]

def solution(gems):
    answer=[]
    start,end=0,0
    set_gem=set(gems)
    while end!=len(gems)-1:
        while len(set(gems[start:end+1]))<len(set_gem) and end<len(gems)-1:
            end+=1
        while not len(set(gems[start:end+1]))<len(set_gem) and start<len(gems)-1:
            start+=1
        print(start-1,end)
        if (len(set(gems[start-1:end+1]))==len(set_gem)):
            answer.append([start,end+1])
    print(answer)
    return(answer[0])

[2차시도 정확성 통과]

# 전체 길이가 1일 경우 append가 안일어나서
# 1차시도에서 인덱스 에러가 발생
# 그리고 무조건 첫값을 보내는 게 아니라 정렬을 해줘야 함.
# 해당 풀이의 문제점은... 슬라이싱을 계속한다는 것이다.
# 슬라이싱이 빠른 연산은 맞지만 O(b-a)로 요소 개수만큼 시간 소요
# 따라서 슬라이싱으로 조회를 해보는 게 아니라, 딕셔너리에 담아두고 관리를 해야 한다...
def solution(gems):
    answer=[]
    start,end=0,0
    set_gem=set(gems)
    while end<len(gems)-1:
        while len(set(gems[start:end+1]))<len(set_gem) and end<len(gems)-1:
            end+=1
        while not len(set(gems[start:end+1]))<len(set_gem) and start<=end:
            start+=1

        if (len(set(gems[start-1:end+1]))==len(set_gem)):
            answer.append([start,end+1])
    if answer:
        return sorted(answer, key =lambda x: x[1]-x[0])[0]
    else:
        return [1,1]

[정답코드]

from collections import defaultdict
def solution(gems):
    start,end=0,len(gems)-1
    left,right=0,0
    dic = defaultdict(int)
    kind = len(set(gems))

    while right<len(gems):
        while len(dic) < kind and right<len(gems):
            dic[gems[right]]+=1 # 여기서 처음에 그냥 right 해서 애먹음
            right+=1
        while len(dic)==kind and left<=right:
            dic[gems[left]]-=1
            if (dic[gems[left]])==0:
                del(dic[gems[left]])
            left+=1
        # right 과 left의 업데이트를 조건문 보다 나중에 써줬기 때문에
        # 실제 만족하는 인덱스는 right-1, left-1이 된다.
        if end-start> right - left:
            start=left-1
            end=right-1
    return[start+1,end+1]