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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67258

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

 

투포인터로 해결하였다.

 

우선 각 보석이 최소 하나가 나와야하므로 보석이 나온 개수를 저장한 딕셔너리를 하나 만들었다.

보석 이름을 키로, 개수를 벨류로 gem_info 딕셔너리를 만들자

 

다음 이제 투포인터로 정답을 구하자.

 

left,right를 0으로 초기화 후 실행한다.

그리고 count라는 개수 변수를 사용한다.

count는 해당 보석이 left, right 사이 구간에서 처음 등장했을 때 값을 증가시킨다.

 

우선 right를 먼저 확인한다.

right 위치의 보석을 확인해서 gem_info에서 개수를 증가시키자.

이때 해당 보석의 개수가 0이라면 전체 count를 1 증가시키자.

그리고 rifght를 1 증가 시키자.

 

count를 변경했으므로 count가 보석의 개수와 같은지 확인한다

그리고 길이에 따른 정답을 갱신한다.

이때 left를 오른쪽부터 확인하므로 길이가 더 작으면 무조건 갱신해주면 된다.

 

다음 left를 확인하자.

우선 left 위치의 보석을 확인해서 gem_info에서 개수를 감소시키자.

left는 구간에서 빠져나오는 포인터이기 때문이다.

그리고 해당 보석의 gem_info의 값을 확인해서 0이 된다면 해당 left, right 구간에서 해당 보석이 없다는 것이다.

따라서 count를 감소시키자.

 

다시 count를 변경했으므로 답을 갱신하자.

 

이 과정을 left가 gems 배열에 끝에 도달할 때 까지 수행하면 된다.

 

def solution(gems):
    gem_info = set_gems_info(gems)
    return calc_length(gem_info, gems)

def calc_length(gem_info, gems):
    left = right = 0
    length = 9876543210
    answer = []

    count = 0
    target_count = len(gem_info)
    while left < len(gems):
        if right < len(gems) and count < target_count:
            gem = gems[right]
            if gem_info[gem] == 0:
                count += 1
            gem_info[gem] += 1
            right += 1
            if count == target_count:
                length,answer = check_answer(answer,length,left,right)

        else:
            gem = gems[left]
            gem_info[gem] -= 1
            if gem_info[gem] == 0:
                count -= 1
            left += 1
            if count == target_count:
                length,answer = check_answer(answer,length,left,right)
    return answer

def check_answer(answer,length,left,right):
    sub = right - left
    if sub < length:
        return sub, [left + 1, right]
    return length,answer
def set_gems_info(gems):
    gem_info = {}

    for gem in set(gems):
        gem_info[gem] = 0

    return gem_info