[카카오] 보석 쇼핑

---

문제 링크

---

def solution(gems):
    answer = []
    
    left = 0
    right = 0
    
    cnt = len(set(gems)) # 총 보석 종류 개수
    dic = {} # key : 보석 이름, value : 보석 개수

    while right < len(gems):
        gem = gems[right]
        if gem in dic:
            dic[gem] += 1
        else:
            dic[gem] = 1
        while left < right:
            gem = gems[left]
            if dic[gem] > 1:
                dic[gem] -= 1
                left += 1
            else:
                break
        if len(dic) == cnt:
            answer += [(left + 1, right + 1)]
        right += 1
    return sorted(answer, key = lambda x: x[1] - x[0])[0]

• 투포인터를 이용

파이썬의 딕셔너리와 집합 자료형을 이용했다.

먼저 left, right를 모두 0으로 두고 right를 +1씩 증가시킨다.
gems의 right 위치에 있는 gem을 딕셔너리 key로 찾아서 value를 증가시킨다.
증가시킨 후, left를 증가시키면서 보석 모든 종류가 포함되지 않기 전까지 해당 보석의 개수를 줄인다.

while left < right:
	gem = gems[left]
    if dic[gem] > 1:
    	dic[gem] -= 1
        left += 1
    else: # 보석을 없애면 종류 개수가 줄어드는 경우
    	break

이후 dic의 길이가 모든 종류의 개수와 같으면 answer 배열에 추가시킨다.
그 후 right += 1 진행 후 while문 반복

---

처음에는 left, right 모두 조건을 만족하는 경우는 left += 1, right -= 1을 진행하고
left만 만족하는 경우 left += 1
right만 만족하는 경우 right -= 1
이런 식으로 구현하였지만

만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

이 조건에서 틀렸다

그래서 일단 조건을 만족하지 않을 때까지 right -= 1을 진행한 후, left += 1을 진행하는 식으로 구현했지만 전혀 틀렸다 . 하하

그래도 투포인터는 떠올렸으니... 복습하장.

---

++ 정확도 100 효율성 0 코드

from collections import deque
        
def solution(gems):
    left = 0
    right = 0
    cnt = len(set(gems))
    answer = 1e9
    set_gem = set()
    for i in range(len(gems) - cnt + 1):
        set_gem.clear()
        for j in range(i, len(gems)):
            set_gem.add(gems[j])
            if cnt == len(set_gem) and answer > j - i:
                left = i
                right = j
                answer = j - i
                break
    
    return [left + 1, right+ 1]

ㅎㅎ 정말 시도 102308129번은 한 듯하다