[코딩테스트][프로그래머스]🔥 프로그래머스 "보석 쇼핑" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 30분

def solution(gems):
    answer = []
    
    start=0
    end=0
    
    types=set(gems)
    typesCnt=len(types)
    
    nowSet=set()
    nowSet.add(gems[end])
    minLength=len(gems)
    answer=[1,len(gems)]
    
    counter=dict()
    counter[gems[0]]=1
    
    while end<len(gems):
        if typesCnt>len(nowSet):
            end+=1
            if end==len(gems):
                break
            if gems[end] not in nowSet:
                counter[gems[end]]=1
                nowSet.add(gems[end])
            else:
                counter[gems[end]]+=1
        elif typesCnt<=len(nowSet):
            if typesCnt==len(nowSet):
                if minLength>(end-start+1):
                    answer=[start+1,end+1]
                    minLength=end-start+1
            prev=gems[start]
            start+=1
            if counter[prev]==1:
                del counter[prev]
                nowSet.remove(prev)
            else:
                counter[prev]-=1

    return answer

보석 쇼핑: 최소 구간 찾기! 💎🛍️

보석 쇼핑을 할 때, 구간을 탐색하면서 전체 종류가 전부 포함되는지를 확인하는 문제로 구간을 시간을 줄여서 한번에 탐색해야 하는 슬라이딩 윈도우 문제이다.

해당 데이터의 갯수가 200,000으로 $N^2$의 시간복잡도를 사용하면 시간초과가 날 확률이 크기 때문에 N으로 탐색하는 방법을 적용시키기로 한다. 해당 전체 확인 종류가 있고 이를 매구간에 걸쳐서 확인해야 하므로 슬라이딩 윈도우를 사용하기로 한다.

만약 종류가 만족하지 않는다면 왼쪽의 끝좌표를 늘려가면서 종류가 만족시킬 때까지 이를 추가한다. 그리고 만약 종류를 만족한다면 현재의 길이를 기록하고 최소가 되게 길이를 하게 하기 위해 앞에서 index를 +1해가면서 길이를 줄여간다.

이렇게 Python으로 프로그래머스의 "보석 쇼핑" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊