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

2020 카카오 인턴십

• Lv 3. 보석 쇼핑 (Python)
  https://school.programmers.co.kr/learn/courses/30/lessons/67258

Code

def solution(gems):
    answer = [0, len(gems) + 1]

    # 특정 범위 물건 모두 싹쓸이 구매
    # 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매

    # 보석 종류 파악
    gem_type_cnt = len(list(set(gems)))

    left = 0
    right = 0

    gem_dict = dict()  # {보석종류 : 빈도수} 형태로 저장

    """투포인터"""
    while (right < len(gems)):

        # right를 움직이며 딕셔너리에 보석 담기 + 빈도수 업데이트 과정
        if (gems[right] not in gem_dict):
            gem_dict[gems[right]] = 1
        else:
            gem_dict[gems[right]] += 1
        right += 1

        # 딕셔너리에 담긴 보석 종류가 전체 보석 종류 개수와 같아진다면 -> left를 움직이며 최소 구간 찾기
        if (len(gem_dict) == gem_type_cnt):

            while (left < right):
                # 현재 left에 있는 보석의 출현 빈도수가 2 이상이라면
                if (gem_dict[gems[left]] > 1):  # 더 짧은 구간을 찾기 위해 right 근처로 left 이동
                    gem_dict[gems[left]] -= 1
                    left += 1

                # 현재 left~right 범위가 answer에 저장된 범위보다 짧다면
                elif (right - left < answer[1] - answer[0]):
                    answer = [left, right]  # answer 범위 업데이트
                    break

                # left를 이동하게 되었을 때 보석 종류가 줄어들게 되는 경우 ->  break
                else:
                    break

    answer[0] += 1  # answer와 범위 비교를 위해서 그냥 저장해뒀던 left를 정답 형식으로 변형 (문제에서는 인덱스가 1부터 시작하기 때문)
    return answer

풀이 및 해설

• 효율성 테스트를 위해서는 결국 투포인터로 풀었어야 하는 문제 ! ! !
• right를 움직이며 하나씩 dict()에 {보석 종류 : 빈도수} 형태로 값을 넣어준다.
• 만약 담아야하는 모든 보석 종류가 dict()에 담겼을 때, left를 움직이며 범위를 파악해간다.
  • 1) 현재 left 위치에 있는 보석 종류가 dict()안에 2개 이상 담겨있다면, left를 이동시켜도 dict()에 담긴 보석 종류에 변동이 없음 → 즉 left 이동 가능 ! (해당 보석 개수는 최소 구간을 위해 하나 줄여도 됨)
  • 2) 현재 left ~ right 범위가 최소 범위라면, answer로 업데이트 (answer에는 최소 범위만 저장해두기)
  • 3) 두 조건에 모두 해당하지 않는다면, left가 이동할 수 없음 → break

이전코드 (슬라이싱, 거의 완전탐색)

• while문을 한번만 돌아서 O(N)이라 생각해서 괜찮을거라고 생각했지만 슬라이싱을 쓰면 안되는 것이었다 . . .
  • 리스트 슬라이싱의 시간 복잡도는 슬라이싱의 범위 길이에 비례한다.

### 효율성 실패 정답

from collections import Counter

def solution(gems):
    answer = []
    
    # 특정 범위 물건 모두 싹쓸이 구매
    # 진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매
    
    # 보석 종류 파악
    gem_type = list(set(gems))  
        
    n = len(gem_type)
    check_min = len(gems)   # 가장 짧은 구간인지 비교하기 위한 변수
    ans_list = []
    
    # 모든 종류가 들어있는 짧은 구간 찾기 (중간에 잘리면 X, 연속되는 구간 중 제일 짧은걸로)
    while(n <= len(gems)):
        keep = True
        # i부터 n만큼 슬라이싱해서 비교
        for i in range(len(gems)):
            flag = True
            if(i+n <= len(gems)):
                sub = gems[i:i+n]
                sub_count = Counter(sub)
                print(sub_count)
                if(len(sub_count) == len(gem_type)):
                    answer = [i+1, i+n]
                    keep = False
                    break
         # 조건에 충족하지 않는다면 슬라이싱 범위 늘리기
        if(keep):
            n += 1
        # 정답을 찾았다면 return
        if(keep == False):
            return answer
    
    return answer

What I learned

• 투포인터 자료

https://blog.naver.com/kks227/220795165570

https://freedeveloper.tistory.com/393

• 코드 해설

https://tech.kakao.com/2022/03/15/2022-newkrew-onboarding-android/05-36/

https://haeseok.medium.com/프로그래머스-보석쇼핑-a901de0ce34

• 정답 코드

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]