[프로그래머스] 파이썬 문제풀이 - [카카오 인턴] 보석 쇼핑

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

프로그래머스

 

첫 풀이

1. 보석 종류 개수부터 gems의 길이까지 늘려가며 모든 경우의 수를 구한다

2. 모든 보석을 갖고있고 구간이 짧은 곳을 찾는다

def solution(gems):
    jw=list(set(gems))
    a,b=100000,200001
    
    for i in range(len(jw),len(gems)+1):
        for j in range(len(gems)-i+1):
            tmp=gems[j:j+i]
            tmp=list(set(tmp))
            if tmp == jw:
                if j+i-(j+1)<(b-a) and a>j+1:
                    a=j+1
                    b=j+i
    return [a,b]

몇몇 경우에서 실패했고 시간초과가 발생했다. 아무래도 모든 경우를 탐색하다보니까 시간이 오래걸린것같다

더 나은 답안

1. head, tail 투 포인터 개념을 사용한다

2. 범위 안에 존재하는 보석의 종류가 전체 종류의 수보다 작으면 tail을 늘려 범위를 늘린다.
3. 범위 안에 존재하는 보석의 종류를 세어 전체 종류의 수와 같으면 head를 늘려 범위를 좁힌다.

4. head와 tail를 이동할때마다 보석 딕셔너리를 갱신해준다

5. 보석의 수가 0이 되면 key를 삭제해준다. 키의 개수를 사용하기 때문 

def solution(gems):
    gem = list(set(gems))
    n = len(gem)
    
    dic = {gems[0]: 1}
    answer = [1, len(gems)]
    left,right = 0,0
    while left <= right and right < len(gems):
        if len(dic) == n:
            if answer[1]-answer[0] > right-left:
                answer = [left+1, right+1]
            
            dic[gems[left]] -= 1
            if dic[gems[left]] == 0:
                del dic[gems[left]]
            left += 1

        elif len(dic) < n:
            right += 1
            if right >= len(gems):
                break
            if gems[right] not in dic:
                dic[gems[right]] = 1
            else:
                dic[gems[right]] += 1
        
    return answer

 

배운 점

1. 범위를 표현하는 문제에서는 투 포인터를 사용하면 편하다