Programmers / 3단계 / 보석 쇼핑 / python

 

https://school.programmers.co.kr/learn/courses/30/lessons/67258

 

 

코드

def solution(gems):
    size = len(set(gems))
    dic = {gems[0]:1}
    temp = [0, len(gems) - 1]
    start , end = 0, 0

    while(start < len(gems) and end < len(gems)):
        if len(dic) == size:
            if end - start < temp[1] - temp[0]:
                temp = [start, end]
            if dic[gems[start]] == 1:
                del dic[gems[start]]
            else:
                dic[gems[start]] -= 1
            start += 1

        else:
            end += 1
            if end == len(gems):
                break
            if gems[end] in dic.keys():
                dic[gems[end]] += 1
            else:
                dic[gems[end]] = 1

    return [temp[0]+1, temp[1]+1]

 

모든 종류의 보석을 1개 이상 포함하는 가장 짧은 구간을 구해야 하는 문제이다. 

시간 복잡도를 고려해 슬라이싱 대신 투포인터와 딕셔너리를 이용하여 풀어야 한다. 

처음에 포인터 start와 end를 모두 1번 진열대에 위치시키고, 보석의 종류가 모두 채워질 때까지 end를 증가시키면서 딕셔너리의 키와 값을 갱신한다. 종류가 모두 채워지면 가장 짧은 구간인지 구하기 위해 start를 증가시키며 비교한다.