[프로그래머스] 보석쇼핑 / Python / 2020 카카오 인턴십

https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3

코딩테스트 연습 - 보석 쇼핑

---

---

Solution

def shopping(gems):
    start, end = 0, 0
    gem_num = len(set(gems))
    gem_dict = {gems[0]: 1}
    result = (0,100001)
    
    while start < len(gems) and end < len(gems):
        if len(gem_dict) < gem_num:
            if end == len(gems) - 1:
                break
            end += 1
            if gem_dict.get(gems[end]) is None:
                gem_dict[gems[end]] = 1
            else:
                gem_dict[gems[end]] += 1
        else:
            if end - start < result[1] - result[0]:
                result = (start+1, end+1)
            if gem_dict[gems[start]] == 1:
                del gem_dict[gems[start]]
            else:
                gem_dict[gems[start]] -= 1
            start += 1
    return result
            
def solution(gems):
    answer = shopping(gems)
    
    return list(answer)

 

투포인터 알고리즘으로 푸는 문제이다. 사실 난 이 문제 풀면서 투포인터를 처음 알았다 👶

유튜브를 좀 찾아보고 적용해서 처음 풀었을 때 정확성 테스트는 통과했지만 효율성 테스트는 거의 전멸을 했다. 머리가 굳어버린 나는 한참 고민하다가 검색을 했고, 맵 자료구조와 투포인터를 통해 풀 수 있다는 것을 알아냈다.

 

gem_dict에 보석이름:빈도수 형태로 담고, gem_dict의 길이를 gem_num과 비교한다. 작을 경우, end를 1 증가 시켜주고, gem_dict에서 해당 보석의 빈도수 또한 1 증가시킨다. 길이가 클 경우, 가장 짧은 구간을 구한 후 gem_dict에서 빈도수를 1 감소 시킨다. 이때 빈도수가 0이 되면 gem_dict에서 제거한다. 그리고 start를 1 증가 시켜준다.