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

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

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

# 프로그래머스 보석 쇼핑

def find_m_gem(jew):
    min_=1000000
    for gem in jew:
        if min_>jew[gem]:
            min_=jew[gem]
            m_gem=gem
    return m_gem


def solution(gems):
    answer = [-1,-1]
    jew = {}
    kinds = len(set(gems))
    for i in range(len(gems)):
        jew[gems[i]] = i
        if len(jew) == kinds:
            m=min(jew.values())
            diff = i-m
            answer[0] = m+1
            answer[1] = i+1
            i+=1
            break
    m_gem=find_m_gem(jew)
    while i<len(gems):
        if m_gem==gems[i]:
            jew[gems[i]]=i
            m_gem=find_m_gem(jew)
        else:
            jew[gems[i]]=i
        m=jew[m_gem]
        if i-m<diff:    
            answer[0]=m+1
            answer[1]=i+1
            diff=i-m
        i+=1
    return answer

일단 모든 보석이 한번 씩 탐색이 된다면, for문을 탈출한다.

가장 앞에 있는 보석(m_gem)과 보석의 위치(jew[m_gem])를 파악한다.

만약에 i 번째 탐색하는 보석이 m_gem과 같은 보석이면, jew[gems[i]]를 갱신한 뒤, 다시 m_gem을 탐색하고,

그렇지 않다면 jew[gems[i]]만 갱신하고 그냥 넘어간다.

 

즉, 가장 최소 index를 계속 갱신하면서, index의 최대와 최소가 가장 작아지는 index를 찾는다.

 

 

 

 

(문제를 좀 더럽게 풀었다... 투 포인터로 깔끔하게 해결하신 다른 분의 풀이를 올린다.)

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]