보석 쇼핑

문제 URL : 코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr)

---

처음 접근

gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] #[3, 7]
# gems = ["AA", "AB", "AC", "AA", "AC"] #    [1, 3]
# gems = ["XYZ", "XYZ", "XYZ"]#    [1, 1]
# gems = ["ZZZ", "YYY", "NNNN", "YYY", "BBB"]#    [1, 5]
def solution(gems = gems):# 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아 구매하기
    answer = []
    gemkind=set(gems) ## O(n)
    anslist=[]
    for i,v in enumerate(gems): # 어짜피 한번은 다 돌아야해
        tmp=[v,]
        tmpidx=[i+1,]
        for j,vv in enumerate(gems[i+1:]):
            ## 나랑 같은게 뒤에도 있는데, 아직 보석을 다 담지 못했어 -> 해당 인덱스부터 시작하는조합은 X야
            if vv == v and len(tmp)<len(gemkind): break 

            if vv not in tmp:
                tmp.append(vv)
                tmpidx.append(i+j+1+1)
        if len(tmp) == len(gemkind) : 
            # tmpidx[-1] - tmpidx[0]
            anslist.append([tmpidx[-1] - tmpidx[0],tmpidx])
    anslist = sorted(anslist, key=(lambda x : (x[0], x[1][0])))
    # print(anslist)
    if len(anslist[0][1])==1:
        ans = [anslist[0][1][0] , anslist[0][1][0]]
    else:
        ans = [anslist[0][1][0], anslist[0][1][-1]]
    return ans

solution()

$O(n^2)$ 의 방법으로 생각했다.
시작은 이러하다. 어떠한 인덱스(i) 에서 시작했을 때, 그녀석부터 뒤로가면서 보석을 담는다.
그런데! 만약, 동일한 보석이 발견됐는데, 아직 보석종류를 다 담지 못했다? 그 말은, i부터 시작하는 보석바구니는 최선의 구간이 아니라는 생각이다.

예를들어 첫번째 테스트케이스를 생각했을 때
gems = ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] 에서, 0번인덱스로 시작을 한다면, j가 1씩 증가하며 보석을 검사한다, 그런데 gems[3]에 'DIA'가 또 발견이 됐다. 아직 에메랄드와 사파이어가 남아있는데 같은 보석을 발견한것이므로, 0번에서 시작하는 보석바구니는 최선의 구간이 아니라는것이다.

그렇게 gems[1] 또한 넘어가고, gems[2]에서 시작하면 RUBY , DIA , DIA, EMERALD, SAPPHIRE 를 발견한 순간, anslist에 붙이고, 다음 이터레이션을 시작한다.

결과는.. 정확도테스트는 다 맞췄으나, 효율성에서 OUT..

---

해결법 : 투포인터

1차원 배열에서 사용 가능하며 $O(n^2)$ 보다 작은 시간복잡도로 풀어야할 때 사용하기 좋은 알고리즘으로, start와 end 포인터를 움직이며 최적의 바구니를 만드는것이라 생가갛면 된다 .
ex. N칸의 1차원배열에서, 그 부분배열 중 원소합이 M이 되는 경우의 수를 구하기
start , end = 0,0으로 시작 , 언제나 start <= end 이어야함
start와 end는 현재 부분배열의 시작과 끝
3-1. 현재 부분합이 M 이상이거나 , 이미 end = N 이라면 :: start ++
3-2. 그렇지 않다면 end ++ 3-3. 현재 부분합이 M과 같다면 결과 ++

위 문제에 적용

s, e 두개의 포인터를 사용
바스켓에 모든 종류의 보석을 담을때까지 e를 이동하며, 바스켓에 추가
매 iteration에서 e를 이동가능한지 체크하여 수행한 수 바스켓이 가득찼는지 (모든종류의 gem을 담았는지) 검사
-> 바스켓이 가득찼다면? -> s를 이동하면서 바스켓에서 하나씩 빼면서 뺼 때마다의 answer가 최적인지 검사

def solution(gems):
    answer = [1,len(gems)]
    s,e = 0,0
    lengem = len(gems)
    gemkind = set(gems)
    if len(gemkind) == 1 : return [1,1]
    basket = {gems[0]:0}
    while s<lengem and e<lengem:
        if len(basket) < len(gemkind): # e 이동
            if basket.get(gems[e]):
                basket[gems[e]] +=1
            else:
                basket[gems[e]] = 1
            e+=1
        while len(basket) == len(gemkind): # s이동
            if basket[gems[s]] > 1:
                basket[gems[s]] -=1
            else:
                del(basket[gems[s]])
            s += 1
            if answer[1]- answer[0] > e-s:
                answer = [s, e]
    return answer
    ```