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

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

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

풀이

처음 접근을 set과 two pointer를 써서 해야겠다고 생각했습니다.

그래서 처음점과 마지막점 범위 리스트를 뽑아서 set으로 형변화 시켜준 뒤 갯수로 비교했는데,,

틀린 점은

첫째, deepcopy하고 set,list 형변환시켜주니까 효율성을 통과 못했습니다.

둘째, 투 포인터 개념을 정확하게 인지 X, 전 범위에 대하여 start ,end 점을 비교해야하는데

처음 end점을 늘려주고 start를 늘려준 뒤 break를 걸어서 정확성에서도 통과를 못했습니다.

 

맞는 풀이

효율성을 위해서

딕셔너리 와 투 포인터를 제대로 사용해야했습니다.

 

딕셔너리로 보석들의 종류와 갯수를 넣어주고

투 포인터로 전 범위 비교하여 짧은 거리를 shortest와 비교

def solution(gems):

    answer=[]
    gems_len=len((set(gems)))
    shortest=len(gems)+1
    first=0
    last=0

    gems_dict={}

    # 전범위를 비교해야하므로 last 증가시키고 first 증가,,,, 또 라스트 증가해서 계속 비교해서 shortest 찾기
    while last<len(gems):
        if gems[last] not in gems_dict:
            gems_dict[gems[last]]=1
        else:
            gems_dict[gems[last]]+=1
        last+=1

        if len(gems_dict)==gems_len:
            while first<last:
                if gems_dict[gems[first]]>1:
                    gems_dict[gems[first]]-=1
                    first+=1
                elif shortest>last-first:
                    shortest=last-first
                    answer=[first+1,last]
                    break
                else:
                    break

    return answer