[프로그래머스] 보석 쇼핑

출처: 프로그래머스 코딩 테스트 연습, [프로그래머스] 보석 쇼핑

새로 알게된 것들

투포인터 알고리즘 : 별건 아니고 그냥 한 반복문 안에 인덱스 2개를 이용해여 앞 뒤로 옮기는 알고리즘이다.
set을 이용해서 푸는데 set론 해결하기 힘든 부분이 있었다. 그래서 len(dic)을 이용해서 보석 종류의 개수를 구했다.
꼭 set만이 해결방안이 아니라는 것을 알게되었다.

풀이

1. 딕셔너리에 만들어 현재 start와 end사이의 보석의 종류별 개수를 저장한다.
2. 만약 딕셔너리에 보석이 없었다면 키와 값을 만들어 넣어주고 이미 존재하는 보석이면 개수를 1 추가해준다. 그리고 end를 1 추가한다.
3. 만약 딕셔너리에 모든 종류의 보석이 존재하면 start의 보석을 딕셔너리에서 1 빼주고 만약 빼준 값이 0이 라면 더 이상 존재하지 않는 것이기 때문에 딕셔너리에서 제거한다. 그리고 start을 1 추가해주고 조건을 만족하는 start와 end이기 때문에 answer리스트에 추가해준다.
4. 단순해 보여도 모든 경우를 모두 확인한다. while문이 돌면서 만약 딕셔너리의 보석의 종류가 전체 보석의 종류의 수보다 작아지는 순간까지 start를 1 추가해줘야한다. 보석의 종류가 줄어들어야 다음 모든 종류의 보석을 다시 탐색할 수 있다. 이 부분의 예외를 잘 확인하지 못해 계속 틀렸다.

코드

def solution(gems):
    N = len(set(gems))
    answer, dic = [], {}
    start, end = 0, 0
    while end < len(gems):
        if gems[end] not in dic:
            dic[gems[end]] = 1
        else:
            dic[gems[end]] += 1
        end += 1
        while len(dic) == N:
            dic[gems[start]] -= 1
            if dic[gems[start]] == 0:
                del dic[gems[start]]
            start += 1
            answer.append([start, end])
        
    return min(answer, key=lambda x: (x[1] - x[0]))

느낀점

분명 문제를 어떻게 푸는지는 알겠는데 끝까지 풀리지 않으면 내일 풀거나 일단 머리를 식히고 풀자.
카카오 레벨 3문제이지만 어느정도 감을 잡을 수 있었고 담에 꼭 풀수 있도록 노력해야겠다.