[코테 공부] 프로그래머스 보석 쇼핑

이 문제는 정확성과 효율성을 둘 다 평가하는 문제였다. 

생각보다 금방 풀어서 제출했는데, 정확성은 100% 정답, 효율성은 66.6% 정답.. 아쉬운 결과

해당 결과의 풀이는 아래와 같다. 

def solution(gems):
    # 결국엔 배열 끝까지 탐색해보아야 함. 
    gem_num = len(set(gems))
    gem_index = dict() # 등장한 가장 나중 인덱스를 저장함. 
    # gem_set = set()
    answer = []
    min_len, min_index, max_index = 1000000, len(gems), 0
    
    for index, gem in enumerate(gems):
        #보석 인덱스 업데이트 
        gem_index[gem] = index+1
        # print(gem_index, gem_set)
        # 셋 내 모든 종류가 포함되는 지 확인 
        if len(gem_index) == gem_num:
            term_len = max(gem_index.values())-min(gem_index.values())
            if term_len < min_len:
                min_len = term_len
                answer = [min(gem_index.values()), max(gem_index.values())]

        # print(answer, min_len)
        
    return answer

 

위 코드에서 줄일 수 있는 부분은 일단 max, min을 계산하는 부분이라고 생각하여 

그 부분을 개선해보...려고 했으나 min 값을 구하는 것을 대체할 수 있는 방법이 생각이 나지 않았다;

 

검색을 해보니 투포인트 방법을 활용해보라고 하여, 다시 구현해보았다. 

def solution(gems):
    # 결국엔 배열 끝까지 탐색해보아야 함. 
    gem_num = len(set(gems))
    gem_index = {gems[0]:1} # 등장한 가장 나중 인덱스를 저장함. 
    s, e = 0, 0
    answer = [0, len(gems)-1]
    
    while s<len(gems) and e<len(gems):
        #아직 보석이 그룹 내 모두 존재하지 않을 경우, 
        if len(gem_index) != gem_num:
            e += 1
            if e == len(gems): break
            if gems[e] not in gem_index:
                gem_index[gems[e]] = 1
            else:
                gem_index[gems[e]] += 1
        #보석이 그룹 내 모두 존재할 경우, 
        else:
            #더 짧은 범위일 경우, 업데이트
            if e-s < answer[1]-answer[0]:
                answer = [s, e]
                
            if gem_index[gems[s]] == 1:
                del gem_index[gems[s]]
            else:
                gem_index[gems[s]] -= 1
            s += 1
            
    answer[0] +=1
    answer[1] +=1
    return answer