김민지

2.문제이름

3. 수행시간[초(s)]

1500

4. git 주소 URL

https://github.com/Min-ji99/BES2-AlgorithmStudy/blob/main/PG/etc/PG_67258.py

좋아요 누르기

좋아요 수

: 0

5 more properties

| 코드 작성하기

def solution(gems) :
    answer=[0, len(gems)-1]
    gem_cnt=len(set(gems))
    gem_dic={gems[0]:1}
    start, end=0, 0
    while start<len(gems) and end<len(gems) :
        if len(gem_dic)==gem_cnt :
            if (end-start)<answer[1]-answer[0] :
                answer=[start, end]
            if gem_dic[gems[start]]==1 :
                del gem_dic[gems[start]]
            else:
                gem_dic[gems[start]]-=1
            start+=1
        else:
            end+=1
            if end==len(gems):
                break
            gem_dic[gems[end]]=gem_dic.get(gems[end], 0)+1
    answer[0]+=1
    answer[1]+=1
    return answer
Python
복사

| 코드 설명하기

gem_cnt : 보석 종류 개수

gem_dic : 선택한 구간에 있는 보석 종류와 해당 보석의 개수

answer 리스트의 초기값을 전체 구간으로 설정한다.

gem_dic의 길이가 보석 종류 개수와 같으면 모든 종류의 보석을 다 갖고 있는 상태이다.

현재 구간의 길이가 answer보다 작으면 값을 갱신해준다.

최소구간을 찾기 위해 start를 1 증가시킨다. 증가시키기 전에 gem_dic에 start 위치의 보석을 하나 빼준다

gem_dic의 길이가 보석 종류와 다르면 더 큰 구간을 확인해야하므로 end를 1 증가시킨다,

이때 end가 gems 범위 밖이면 반복문을 종료한다.

end 위치의 보석을 gem_dic에서 1 증가시켜야한다.

2~3번을 start와 end가 gems 리스트 범위 안에 있으면 계속 반복한다.

구간은 1부터 시작해야하므로 1증가시키고 반환한다.