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

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

프로그래머스

문제를 간략히 요약하면 다음과 같다.

보석이 진열대에 놓인 정보를 나타내는 gems 배열이 주어질 때, 몇 번에서 몇 번까지 구매를 해야 모든 종류의 보석을 살 수 있는지 거리에 대한 최솟값을 반환해야 한다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 투포인터 알고리즘을 사용하기 위해 시작점 start와 끝점 end를 설정한다.

2. 모든 종류의 보석을 구매해야하기 때문에, 중복을 제거하는 set을 사용하여 보석의 종류의 갯수를 구한다.

3. 최솟값을 구해야하기 때문에, 값을 구하고 최솟값을 다시 초기화하는 방식으로 진행할 것이다. 따라서 초기에서 움직일 수 있는 가장 큰 수인 gems이 배열크기를 가장 작은 값으로 설정한다.

4. end 포인터를 하나씩 뒤로 이동하며 딕셔너리 값에 +1을 해준다.

5. 딕셔너리의 크기와 보석의 종류가 같을 때가 모든 보석을 구매했을 때이다.

6. 5번일 때, start 포인터에 해당하는 딕셔너리 값이 2 이상이면 뒤로 한 칸 물러도(해당 보석의 구매 횟수를 -1 해줘도) 모든 종류의 보석을 구매한 것이기 때문에, start+1를 해줘서 뒤로 한칸 이동한다.(start 값을 뒤로 이동하면 할수록 end와의 차이가 작아져서 최솟값이 훨씬 더 작아진다.)

7. 초기에 설정한 최솟값보다 end-start가 작다면 end-start가 최솟값이 되므로 정답을 찾은 것이다. 따라서 break를 해준다. 

def solution(gems):
    answer = []
    check={}
    start=0 #1번
    end=0
    kind=len(set(gems)) #2번
    short=len(gems) #3번
    while end<len(gems):
        if gems[end] not in check: #4번
            check[gems[end]]=1
        else:
            check[gems[end]]+=1
        end+=1
        
        if len(check)==kind: #5번
            while start<end:
                if check[gems[start]]>1: #6번
                    check[gems[start]]-=1
                    start+=1
                elif short>end-start: #7번
                    short=end-start
                    answer=[start+1,end] #end가 end+1이 아닌 이유는 솔직히 잘모르겠습니다.
                                         #케이스에서 값이 1차이 나길래 빼줬더니 답이 되었네요.. 혹시나 아시는 분은 댓글로 알려주면 감사하겠습니다!
                    break
                else:
                    break
    return answer

 

투포인터 알고리즘을 사용해야 런타임에러가 발생하지 않는 문제였다.

참고로 필자는 투포인터 알고리즘을 사용하기 전에 DFS를 사용하여 코드를 작성하였는데,

테스트 케이스는 통과했으나, 2문제를 제외한 모든 케이스가 다 런타임에러가 발생하였다.(상당히 슬펐어요 진짜 ㅠㅠ 다 짜고 엄청 뿌듯했었는뎅 ...)

그래도 시간복잡도가 낮은 경우에는 모두 통과하는 것으로 보아 코드의 정확성에는 문제가 없기 때문에 DFS로도 이렇게 풀 수 있다는 것을 보여주기 위해 코드를 첨부하겠다.

def solution(gems):
    answer = []
    dap=[]
    dfs(0, gems, dap, len(gems))
    return [dap[0][0],dap[0][1]]

def dfs(index, gems, dap, temp):
    stack=[]
    for i in range(index,len(gems)):
        if len(list(set(gems)))>len(gems)-index:
            return
        stack.append(gems[i])
        if len(list(set(stack)))==len(list(set(gems))):
            distance=i-index
            if distance<temp:
                if dap:
                    dap.pop()
                dap.append([index+1,i+1,distance])
                temp=distance
        
        dfs(index+1, gems, dap, temp)