프로그래머스: 보석 쇼핑

문제

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

 

문제 풀이

 진열된 보석들 중 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제이다. 앞에서부터 순차적으로 탐색을 하게 되면 효율성을 통과할 수 없다. 고민을 하다가 솔루션을 참조하였는데, 투포인터를 사용하여야 하는 문제였다.

 

 구현하는 방식은 솔루션과 같이 구현하면, 문제를 해결할 수 있다. 평소 투포인터를 활용하는 문제를 다루어보지 않아 풀이를 보고 나서야 이해를 할 수 있었다.🤔

 

코드

def solution(gems):
    start, end = 0, 0
    gem_num = len(set(gems))
    gem_dict = {gems[0]: 1}
    answer = [0,len(gems)]
    
    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 < answer[1] - answer[0]:
                answer = [start+1, end+1]
            if gem_dict[gems[start]] == 1:
                del gem_dict[gems[start]]
            else:
                gem_dict[gems[start]] -= 1
            start += 1
            
    return answer