2020 카카오 인턴십 - 보석 쇼핑, 파이썬

문제

---

• 프로그래머스 카카오 코딩 테스트 문제 링크

풀이

---

• 난이도 : 레벨 3
• gems 배열 크기는 최대 100,000 이기 때문에 O(N^2)으로 풀면 시간 초과가 난다.
• 따라서 start, end 두개의 포인터를 조작하는 투포인터 알고리즘을 활용
• 보석의 종류별로 최소 1개 이상의 수량이 있을 때까지 right를 1씩 더해줌
• 최소 1개 이상의 수량이 확보되었으면 left를 1씩 움직여가며 중복된 보석을 제거해줌
• gems 배열 끝까지 위 단계를 반복해 cand 배열에 넣은 후 구간 길이가 짧고, 같다면 left 크기가 작은 원소를 리턴한다.

코드

---

from collections import defaultdict

def solution(gems):
    cand = []
    left = right = 0
    N, gem_num = len(gems), len(set(gems))
    dic = defaultdict(int)
    while left <= right:
        # len(dic)은 dic의 key 값의 수, gem_num은 보석의 종류, 즉 두개가 같아야 left를 움직여줌
        if len(dic) == gem_num:
            # dic[gems[left]] == 1이란 뜻은 해당 left 위치에서 더이상 움직일 수 없다는 뜻(최소 1개 수량 확보 불가능)
            if dic[gems[left]] == 1:
                cand.append((left + 1, right, right - left))
                del dic[gems[left]]
            else :
                dic[gems[left]] -= 1
            left += 1
        else:
            if right == N :
                break
            dic[gems[right]] += 1
            right += 1
    cand.sort(key = lambda x: (x[2], x[0]))
    return cand[0][:2]