[프로그래머스] 보석 쇼핑

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

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

 

효율성 실패

def solution(gems):
    # 이진탐색으로 몇개를 확인할지부터 찾자
    # 1. x개를 탐색했는데 찾았다. -> 찾는 갯수를 줄여
    # 2. x개를 탐색했는데 못찾았다. -> 찾는 갯수를 늘려
    # 찾을 때마다 [찾는 갯수, [찾은 갯수의 시작 진열대 번호, 끝 진열대 번호]]
    # 진열대 번호를 적는거는 맨 처음 것만
    ans=[]

    start=0
    end=len(gems)

    count_gems=len(set(gems))

    while start<=end:
        middle=(start+end)//2

        start_index=-1
        end_index=-1

        for i in range(len(gems)-middle+1):
            temp_set=set(gems[i:i+middle])
            if len(temp_set)==count_gems:
                start_index=i
                end_index=i+middle-1
                break

        if start_index != -1: # 찾았을 때
            ans.append([middle,[start_index+1, end_index+1]])
            end=middle - 1
        else: # 못 찾았을 때
            start=middle + 1

    if ans==[]:
        ans.append([end, [1, end]])

    ans.sort()
    return ans[0][1]

주어진 테스트 케이스는 다 성공했지만, 효율성은 하나빼고 다 실패

 

카카오에서 제공한 풀이 방법.. 어렵다

 

효율성, 테스트 케이스 다 성공

def solution(gems):
    size=len(set(gems))
    d_size=len(gems)
    dic={gems[0]:1}
    temp=[]
    l_idx, r_idx = 0,0

    while (l_idx<d_size and r_idx<d_size):
        if len(dic) < size:
            r_idx+=1
            if r_idx==d_size:
                break
            dic[gems[r_idx]]=dic.get(gems[r_idx],0)+1

        else:
            temp.append((r_idx-l_idx, [l_idx+1, r_idx+1]))
            dic[gems[l_idx]]-=1
            if dic[gems[l_idx]]==0:
                del dic[gems[l_idx]]
            l_idx+=1

    temp=sorted(temp, key=lambda x: (x[0], x[1]))

    return temp[0][1]