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

문제

진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이 때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return하도록 solution 함수를 완성해주세요.
가장 짧은 구간 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

제한사항

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

풀이

투 포인트를 사용해서 풀었습니다.

코드

def solution(gems):
    answer = []
    kind = set()
    for gem in gems:
        kind.add(gem)
    kind_no, left, right = len(kind), 0, 0
    picked = {gems[0]: 1}
    minLength = len(gems) + 1
    while True:
        if len(picked) == kind_no:
            if right-left+1 < minLength:
                minLength = right-left+1
                answer = [left+1, right+1]
            picked[gems[left]] -= 1
            if picked[gems[left]] == 0:
                picked.pop(gems[left])
            left += 1
            if right < left: break
        else:
            right += 1
            if right == len(gems):
                break
            if gems[right] in picked:
                picked[gems[right]] += 1
            else:
                picked[gems[right]] = 1
    return answer