문제

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

개발자 출신으로 세계 최고의 갑부가 된 어피치는 스트레스를 받을 때면 이를 풀기 위해 오프라인 매장에 쇼핑을 하러 가곤 합니다.
어피치는 쇼핑을 할 때면 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매하는 습관이 있습니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

예를 들어 아래 진열대는 4종류의 보석(RUBY, DIA, EMERALD, SAPPHIRE) 8개가 진열된 예시입니다.

진열대 번호 1 2 3 4 5 6 7 8
보석 이름 DIA RUBY RUBY DIA DIA EMERALD SAPPHIRE DIA
진열대의 3번부터 7번까지 5개의 보석을 구매하면 모든 종류의 보석을 적어도 하나 이상씩 포함하게 됩니다.

진열대의 3, 4, 6, 7번의 보석만 구매하는 것은 중간에 특정 구간(5번)이 빠지게 되므로 어피치의 쇼핑 습관에 맞지 않습니다.

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

내가 푼 풀이(실패)

            
def solution(gems):
    global left, right
    answer = []
    n = list(set(gems))
    arr = dict()
    for idex , name in enumerate(gems):
        if name in arr:
            arr[name].append(idex)
        else:
            arr[name] = [idex]
    # 한개짜리 찾아주기
    primary = []
    for name, cnt in arr.items():
        if len(cnt) == 1:
            primary.append(arr[name][0])
    left = len(gems)//2
    right = len(gems)//2
    if len(set(gems))==1:
        return [1,1]
    
    if len(primary) != 0 :
        left  = min(primary)+1
        right = max(primary)+1
        print(left,right)
        left,right = dfs(gems,left,right)
            
    return [left,right]

def dfs(gems,left,right):
    if set(gems[left:right+1]) == set(gems):
        print(set(gems[left:right]))
    return [left,right]
   

기본적으로 문제를 읽었을때 투포인터의 느낌이 매우 강했다.
그래서 하나짜리는 무조건 들어가야하고 그 사이에 만약에 다 존재할지 출력
그 이후는 하나씩 왼쪽 오른쪽을 늘려가며 백트래킹을 하려고했다.
하지만 아마 백트래킹 자체가 시간복잡도가 크기 때문에
효율성에서 실패하지 않았나 싶다.

다른 사람 풀이(참고)

def solution(gems):
    
    n = len(gems)
    answer = [0,n-1]
    kind = len(set(gems)) # 모아야하는종류
    dic = {gems[0]:1}
    start, end = 0,0 # 처음에서 동시에 시작
    # end는 늘려가는 용도 start는 줄이는 용도
    while start < n and end< n:
        # 아직 모아야할 종류 부족
        if len(dic) < kind:
            end +=1
            if end == n:
                break
            dic[gems[end]] = dic.get(gems[end], 0) +1 # 이 부분이 새로웠음
        else: # 종류를 다 채웠으면 크기를 비교하고 start point 증가 & dic 앞에 하나제거
            if (end-start+1) < (answer[1] - answer[0] +1):
                answer = [start, end]
            if dic[gems[start]] ==1:
                del dic[gems[start]]
            else:
                dic[gems[start]] -=1
                
            start +=1
            
    answer[0] +=1
    answer[1] +=1
    return answer

알게된 것
dic.get(찾길 원하는것 , default value) # default 값 설정이 가능하다 if 문 사용 x

투포인터로 해결을 하였고
차이점은 처음부터 start는 거리를 줄이는 용도 end 는 거리를 넓혀서 종류를 채우는 용도 였다.
그리고 끝까지가면 끝나는 그런 풀이 방식이였다.
알고리즘은 맞았지만 처음부터 탐색을 한다는 접근 방식에서 달랐다.
추가로

del dic[gems[start]]

처럼 get을 통해 default value를 줄 수 있지만
지우는건 직접 del을 사용하여 지워야한다.

투포인터 문제 연습을 더 해야겠다... 판별이 가능한 만큼 익숙해지면 쉬울테니깐...