프로그래머스 보석 쇼핑(투포인터 알고리즘) with Python

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

프로그래머스

어떻게 풀어야할지 잘 모르겠어서 (시간초과되는 로직밖에 생각이 안남ㅠㅠㅠ) 다른 사람들의 풀이를 보고 참고해 풀었다.

이 문제는 투포인터 알고리즘을 사용하여 풀어야 하는 문제였다!

투포인터 알고리즘이란?

리스트에 순차적으로 접근을 할 때 start index와 end index를 정해서 옮겨가면서 접근하는 방식이다.

위에 문제에서는 start index와 end index를 옮겨가면서 해당 인덱스 사이에 보석들의 종류가 다 있는지 확인하고 있다면

현재 answer에 저장되어있는 start index와 end index를 비교해서 더 짧은 인덱스로 갱신시키는 방식으로 쓰였다.

이 때 리스트 슬라이싱을 사용하면 시간초과가 나게 되므로 딕셔너리를 사용해 풀었다. (리스트 슬라이싱은 깊은 복사하는 방식이기 때문에 시간이 오래 걸림)

def solution(gems):
    N = len(gems)
    answer = [0, N-1]
    # 전체 보석 종류
    kind = len(set(gems))
    # 종류 체크할 딕셔너리
    dic = {gems[0]:1,}
    # 투포인터
    s, e = 0, 0
    # start index와 end index가 모두 N안에 있을 때
    while s<N and e<N:
        # 보석 종류가 모자라면 end index를 하나 늘림
        if len(dic) < kind:
            e += 1
            if e == N:
                break
            # end index에 해당하는 dic에 보석이 있으면 +1 없으면 0
            dic[gems[e]] = dic.get(gems[e], 0) + 1
        # 보석 종류가 다 채워지면
        else:
            # 현재 정답에 저장된 길이보다 짧으면
            if (e-s+1) < (answer[1]-answer[0]+1):
                answer = [s, e]
            # 만약 맨 앞에 빼야되는 보석이 한개 있으면 dic에서 삭제
            if dic[gems[s]] == 1:
                del dic[gems[s]]
            # 아니면 개수만 하나 빼줌
            else:
                dic[gems[s]] -= 1
            # start index를 하나 늘림
            s += 1
            
    answer[0] += 1
    answer[1] += 1
            
    return answer