문제

풀이

효율성 테스트를 통과하기 위해서 알고리즘을 잘 세워야 한다. 투 포인터 알고리즘을 이용해서 통과했다. 구매를 시작하는 진열대와 종료하는 진열대의 인덱스를 각각 포인터로 삼아서 선택된 구간의 보석 수를 딕셔너리로 저장한다. 이때 구매하지 못한 보석이 있다면 오른쪽 포인터를 이동시키고, 모든 보석을 구매했다면 길이와 시작 인덱스를 비교하여 정답을 갱신한다.

알고리즘은 올바르게 작동했지만 테스트 케이스 13과 15의 시간 조건이 매우 빡빡해서 여기서 시간을 더 줄여야 했다. 그래서 보석을 모두 구매한 경우 중복된 원소를 최대한 제거하여 최적화하는 코드를 추가해 주었다.

코드

def solution(gems):
    N = len(gems)
    kinds = set(gems)
    n = len(kinds)
    check = {gem : 0 for gem in kinds}
    l = r = 0
    check[gems[l]] += 1
    answer = [1, N]
    while l < N:
        if r - l + 1 < n or 0 in check.values():
            if r >= N - 1:
                break
            r += 1
            check[gems[r]] += 1
        else:
            while check[gems[l]] > 1:
                check[gems[l]] -= 1
                l += 1
                if l >= N:
                    if (r - l) < (answer[1] - answer[0]):
                        answer = [l + 1, r + 1]
                    return answer
            if (r - l) < (answer[1] - answer[0]):
                answer = [l + 1, r + 1]
            else:
                check[gems[l]] -= 1
                l += 1
    return answer

사족

투 포인터 알고리즘은 시간복잡도가 $O(n)$이라 웬만하면 시간 내에 해결이 되는데 테스트 케이스가 엄청 빡빡하게 설정되어 있어서 최대한 시간을 깎아내느라 애를 썼다.

그리고 어피치는 대체 뭘 개발했길래 개발자 출신으로 저 정도의 갑부가 된 걸까...