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

🔔 문제

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

🎯 풀이방법

변수

• jewerly : 현재 구간에 포함되어 있는 보석 종류 (dictionary)
• jewerly_type : 보석의 총 종류수
• start, end : 시작점, 끝점
• shortest : 최단거리
  
  

idea

모든 종류의 보석을 포함할 때까지 끝점(end)을 증가한 뒤, 해당 구간이 최단거리가 되도록 시작점을 증가한다.

1. 모든 변수 초기화
2. 현재 구간(start~end)의 보석 종류 update
3. 끝점 증가
4. 만약 현재 구간의 보석종류가 총 보석 종류와 같다면,
   4-1. 적어도 시작점의 보석이 2개 이상 존재한다면 시작점 증가
   4-2. 기존 최단거리보다 현재 구간의 거리가 짧다면 최단거리 update
5. 2~4 과정 을 끝점이 맨 끝에 도달할 때까지 반복한다
   
   

💡 이 문제를 통해 얻어갈 것

투포인터 문제

💻 Python 코드

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

    start,end = 0,0

    jewerly_type = len(set(gems))  # 보석의 총 종류수
    jewerly = {}  # 현재 구간에 포함되어 있는 보석 종류

    while end < len(gems):
        # 현재 보석 종류 update
        if gems[end] not in jewerly:
            jewerly[gems[end]] = 1
        else:
            jewerly[gems[end]] += 1

        end += 1

        # 현재 구간의 보석종류 = 총 종류수
        if len(jewerly) == jewerly_type:
            # start가 end보다 같을 때까지 증가
            while start < end:
                if jewerly[gems[start]] > 1:  # 2개 이상 있는 거
                    jewerly[gems[start]] -= 1
                    start += 1

                # 기존 구간 최단거리 > 현재 구간거리
                elif shortest > (end-start):
                    shortest = end-start
                    answer = [start+1, end]
                    break
                else:
                    break
    return answer