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

문제

• 매장 진열대의 특정 범위의 물건들을 모두 싹쓸이 구매한다.
• 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아 구매해야 한다.
• 1 <= 보석 개수 <= 100,000

 

풀이 1

• 2중 배열로 모든 보석을 포함할 수 있는 시작-끝 찾기

정확성 테스트 통과, 효율성 테스트 실패

def solution(gems):
    g = len(set(gems))
    n = len(gems)
    answer = []
    
    if g == 1 :
        return (1, 1)
    
    for i in range(n) :
        gem_list = {gems[i]}
        for j in range(i+1, n) :
            if gems[j] not in gem_list :
                gem_list.add(gems[j])
            if len(gem_list) == g :
                answer.append((i+1, j+1))
                break
            
    return sorted(answer, key=lambda x : (x[1]-x[0]))[0]

 

풀이 2

• 투 포인터로 리스트의 처음(left)과 끝(right)을 동시에 확인하기
  • 모든 보석을 포함하지 않았다면 right 를 늘리고
  • 모든 보석을 포함한 경우면 정답 업데이트 하고 left 하나 늘리기
• 정답은 left, right가 뒤바뀌기 전까지 그리고 정답이 최소화 가능성이 있는 경우에만 찾도록 한다.

 

from collections import defaultdict

def solution(gems):
    n = len(gems)       # 전체 보석 개수
    g = len(set(gems))  # 보석 종류 개수
    answer = [1, n] 
    
    gem_dic = {gems[0] : 1} # 보석 종류별 개수 카운팅
    left, right = 0, 0      # 왼쪽, 오른쪽 포인터
    
    # 정답 구간이 최소화 가능성이 있는 경우 반복
    while left <= right or answer[1]-answer[0] > g:
        # 모든 보석을 포함하는 구간 발견
        if len(gem_dic) == g :  
            if answer[1]-answer[0] > right-left :   # 정답 최소화 가능한지 확인
                answer = [left+1, right+1]
            
            # left 한 칸 앞으로
            gem_dic[gems[left]] -= 1
            if gem_dic[gems[left]] == 0 :
                del gem_dic[gems[left]]
            left += 1
        # right 한 칸 앞으로
        elif right < n-1 :
            right += 1
            if gems[right] in gem_dic :
                gem_dic[gems[right]] += 1
            else :
                gem_dic[gems[right]] = 1
        # 둘 다 못하면 더이상 가능성 탐색 불가능한 경우
        else:
            break
    return answer

 

References

• 프로그래머스 Lv3 보석 쇼핑