보석 쇼핑

문제

---

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

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

 

 

나의 풀이

---

처음엔 그냥 2중 for문을 써서 각 시작점마다 보석 종류를 모두 포함하는 끝지점을 검출하면 break하고 다음 시작점부터 탐색하는 알고리즘을 짰는데 역시나 시간초과에 걸렸다. 개선한 풀이는 다음과 같다.

1. start, end의 투포인터를 사용한다. 처음엔 둘다 0번째 인덱스로 초기화 한다.
2. start부터 end까지의 보석이 전체 보석 종류를 포함하면 start를 증가시키고, 모자라면 end를 증가시킨다.
3. 포인터를 증가시키면서 전체 보석을 포함하는지의 여부는 dictionary로 파악한다. (start를 증가시켜야하면 dic[start] -= 1해주고 end를 증가시켜야하면 dic[end] += 1 해준다. 즉, dictionary는 해당 범위의 보석들의 빈도수이다.)
4. 이 때, dic[i]==0이면 해당 key i를 dic에서 del 해주어야 한다.

 

코드

---

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]