[프로그래머스/파이썬] 보석 쇼핑(67258) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 보석 쇼핑(67258)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

보석 배열에서 모든 종류의 보석을 최소 1개 이상 포함하는 가장 짧은 구간 [start, end](1-indexed)을 찾는 문제입니다.

길이가 같으면 시작 인덱스가 작은 구간을 선택합니다.

코드

def solution(gems):
    answers = []
    gem_set = set(gems)

    last = 0

    while last + len(gem_set) - 1 < len(gems):

        start, end, last = last, last + len(gem_set) - 1, len(gems)
        gem_dic = dict()
        
        for i in range(start, end):
            try: gem_dic[gems[i]] += 1
            except: gem_dic[gems[i]] = 1

        while end < len(gems):
            try: gem_dic[gems[end]] += 1
            except: gem_dic[gems[end]] = 1
            if len(gem_dic.keys()) == len(gem_set): break
            end += 1
            
        while start <= end and len(gem_dic.keys()) == len(gem_set):
            gem_dic[gems[start]] -= 1
            if gem_dic[gems[start]] <= 0: del gem_dic[gems[start]]
            if len(gem_dic.keys()) < len(gem_set):
                answers.append([start+1, end+1])
                last = start + 1
                break
            start += 1

        if end - start + 1  == set(gems): return [start+1, end+1]

    return min(answers, key = lambda x:(x[1]-x[0], x[0], x[1]))

print(solution(	["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))
print(solution(["ZZZ", "YYY", "NNNN", "YYY", "BBB"]))
print(solution(["SE", "PUSS", "PUSS", "BOO", "SE"]))
#print(solution(["DIA"]))
#print(solution(["DIA", "DIA"]))

설명

전체 보석 종류 수를 set(gems)로 구한 뒤, 현재 구간 내 보석 개수를 딕셔너리로 관리합니다.

• 오른쪽 포인터를 늘려 모든 종류를 포함할 때까지 확장
• 왼쪽 포인터를 줄여 가능한 한 짧은 유효 구간으로 축소

이 과정을 반복하며 후보 구간을 모은 뒤 길이, 시작점, 끝점 기준으로 가장 작은 구간을 반환합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---