[프로그래머스] - 보석 쇼핑(파이썬)

알고리즘이 생각이 안나 힌트에서 어떤 알고리즘 써야되는지 확인함

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

프로그래머스

 

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

[제한사항]

• gems 배열의 크기는 1 이상 100,000 이하입니다.
  • gems 배열의 각 원소는 진열대에 나열된 보석을 나타냅니다.
  • gems 배열에는 1번 진열대부터 진열대 번호 순서대로 보석이름이 차례대로 저장되어 있습니다.
  • gems 배열의 각 원소는 길이가 1 이상 10 이하인 알파벳 대문자로만 구성된 문자열입니다.

---

해설

투포인터의 개념을 알면 생각보다 굉장히 쉬운 문제인 것 같다.
투포인터의 개념을 찾아보면서 슬라이딩 윈도우에 대해서도 알게 됬는데, 이 둘의 차이점을 간단하게 말하면 다음과 같다.
특정 구간이 가변적이냐? 그러면 투포인터, 고정적이냐? 그러면 슬라이딩 윈도우라고 생각하면 편하다. 

따라서 본 문제는 투포인터를 이용해야한다.

1. 보석 종류의 갯수 파악을 해야한다.

2 - 1. 반복문을 돌면서 보석이 부족하면 오른쪽포인터를 + 1 시킨다.

2 - 2 - 1. 반복문을 돌면서 보석이 충분하면 왼쪽포인터를 + 1 시킨다.

2 - 2 - 2. 왼쪽 포인터를 옮겼을때 보석이 부족해지면 정답 후보군이므로 왼쪽포인터,오른쪽포인터,길이를 임시 저장해준다.

위에 조건을 반복하면 된다.

한가지 주의할 점은 이 문제는 시간효율성도 따지므로 보석 종류의 갯수 파악 및 보석이 충분한지,부족한지의 여부도 가장 빠른 시간안에 알아내어야한다.

def solution(gems):
    gemLength = len(gems)
    sets = set(gems)
    gemCount = len(sets)

    countMap = {}
    for key in sets:
        countMap[key] = 0
    sets = set()
    lPointer = 0
    rPointer = 0

    minLength = 10**9
    start = 10**9
    end = 0

    while lPointer <= rPointer:
        # 모든 보석이 있는지 확인
        if not len(sets) == gemCount:
            # 없으면rPointer하나 올리고 카운트
            if rPointer >= gemLength:
                break
            countMap[gems[rPointer]] += 1
            sets.add(gems[rPointer])
            rPointer += 1
        else:
            # 모든 보석이 다 있으면 일단 left를 계속 +1 시키면서 조건 확인
            countMap[gems[lPointer]] -= 1
            if countMap[gems[lPointer]] <= 0:
                sets.remove(gems[lPointer])
                # 조건이 위배되는 순간 한쌍을 저장 시켜 놓음
                length = rPointer - lPointer
                if length < minLength:
                    minLength = length
                    start = lPointer
                    end = rPointer
                elif length == minLength and lPointer < start:
                    start = lPointer
                    end = rPointer
            lPointer += 1

    return [start + 1, end]