[programmers] 보석쇼핑

---

로직

1. 투포인트 기법을 사용해야한다. 아니면 효율성에서 걸린다. (나한테는 낯설고 어려웠던 문제,,,ㅠ)

2. 보석을 다 안가지고 있으면 end를 올려주고 보석을 다 가지고 있으면 start를 올려준다고 생각하면 된다.

3. 로직 설명

• 모든 보석을 가지고있지 않다면, end를 하나씩 늘려서 다음 보석을 가진다. 
• 모든 보석을 가지고 있다면, start, end의 차이가 최소가 되는 경우로 갱신한다. 
• 갱신한 후에는 start를 한칸 씩 옮기면서 더 최소를 만들 수 있는지 확인한다. check = dict()에서 갯수를 확인하며, start를 한칸씩 올리기때문에 범위 안에 들어오지 않게 되는 보석은 갯수를 내려준다.
• 이때 만약에 보석이 0개가 되었다면, check에서 지워주고 다시 그 보석이 생겨 모든 보석이 1개 이상이 될때까지 나아간다.
•  

코드

def solution(gems):
    gems_set = len(set(gems))  # {D, R, E, S}
    start, end = 0, 0
    check = {gems[0]: 1}
    answer = [0, len(gems) - 1]
    # [0, len(gems)]하면 맨 밑에서 answer[1], answer[0] += 1씩 해주기 때문에 보석 쇼핑이 맨 마지막에서 끝나면 len(gems)=6이더라도 답이 [,7]로 나온다
    while start < len(gems) and end < len(gems):

        if len(check) == gems_set:
            if answer[1] - answer[0] > end - start:
                answer[1] = end
                answer[0] = start
            if check[gems[start]] != 1:
                check[gems[start]] -= 1
                start += 1
            elif check[gems[start]] == 1:
                del check[gems[start]]  # 여기에서 값을 지워줘야 다음으로 넘어갈 수 있다.
                start += 1

        # while을 돌면서 len(check) < gems_set을 처리하는게 아니라
        # 마지막에 보석을 다 모으게 되면 while을 돌면서 start를 올려줘야한다.
        # 마지막에 보석을 다 모으면 end + 1상태로 끝나서 elif len(check)==gems_set에 안걸린다.
        # 따라서 if end == len(gems): break 를 while문 밑에다 하는게 아니라 end += 1하고난 후에 비교해야함
        if len(check) < gems_set:
            end += 1
            if end == len(gems):
                break

            if check.get(gems[end]) is None:  # 중복이 많아지면 n번 돌기때문에 효율성 꽝
                check[gems[end]] = 1
            else:
                check[gems[end]] += 1

    answer[0] += 1
    answer[1] += 1

    return answer

 

주의해야할 점

1. ** 문제점 : answer = [0, 0]에서 시작하는 것이 아니라 answer = [0, len(gems) - 1]에서 시작해야한다.

   ** 이유 : 1) [0, 0]이면 이미 가장 작은 값이기 때문에 start, end를 갱신하고 가장 짧은 값을 구할 때 구할 수가 없다.

               2) [0, len(gems)]하면 맨 밑에서 answer[1], answer[0] += 1씩 하기 때문에 만약 보석 쇼핑이 맨 마지막에서

                   끝나면 len(gems)=6이더라도 답이 [start, 7]로 나온다(len(gems)보다 긴 값이 나와버린다.)

 

2. ** 문제점 : 시간초과

   ** 이유 : check = [], num = 0이라 두고 check에 gems를 매번 집어넣고, 그 다음값들 중에 없는 애들만 num+=1

               하면서 gems_set과 비교하게된다면, 거의 완전탐색이 되고, 그것은 O(n^2) 하면 100억이니까 시간초과

   ** 해결책 : check = {'D' : 1}이런식으로 dictionary로 두어 확인. 리스트에 넣으면 start점이 바뀔 때마다 처음으로

                 갱신해야하는데 중복이 많아지면 n번 돌기때문에 효율성 꽝이다.

 

3. ** 문제점 : 딕셔너리로 바꿨을 때 풀이

   ** 예시 : 

        ex. d,r,r,d,d,e,s,d,d,e,s,r이 테케라면
        [d,r,r,d,d,e,s],d,d,e,s,r
        d,[r,r,d,d,e,s],d,d,e,s,r
        d,r,[r,d,d,e,s],d,d,e,s,r -> [2, 6] (5)
        d,r,r,[d,d,e,s,d,d,e,s,r]
        d,r,r,d,[d,e,s,d,d,e,s,r]
        d,r,r,d,d,[e,s,d,d,e,s,r]
        d,r,r,d,d,e,[s,d,d,e,s,r]
        d,r,r,d,d,e,s,[d,d,e,s,r]
        d,r,r,d,d,e,s,d,[d,e,s,r] -> [8, 11] (4)
        이렇게 나오게하려면 앞에 값을 삭제하고 뒤에 나오는 값들을 다시 넣어줘야한다.

   ** 해결책 :

         if check[gems[start]] != 1:

             check[gems[start]] -= 1
             start += 1
         elif check[gems[start]] == 1:
             del check[gems[start]]

 

    [0, 6] -> [1, 6] -> [2, 6]가 된다. 이때, [8, 11]까지 가려면, {'DIA': 2, 'RUBY': 1, 'EMERALD': 1, 'SAPPHIRE': 1}에서

    gems[2]의 'RUBY'를 지우고 다시 'RUBY'가 나오는 gems[11]까지 check에 넣어야한다.

 

4. ** 문제점 : 테케 6, 7번 에러

   ** 이유 : 내가 쓴 코드에선 while을 돌면서 len(check) < gems_set을 처리한다.

               이렇게 된다면, 마지막에 보석을 다 모으면 end + 1상태로 끝나서 elif len(check)==gems_set에 안걸린다.

               그치만 난 확인이 필요하다.

   ** 해결책 : 마지막에 보석을 다 모으게 되면 while을 돌면서 start를 올려줘야한다.

                  따라서 if end == len(gems): break 를 while문 밑에다 하는게 아니라 end += 1하고난 후에 비교해야함