[알고리즘] 프로그래머스 - 보석 쇼핑

프로그래머스 (2020 카카오 인턴쉽) - 보석 쇼핑

내 풀이

import sys


def solution(gems):
    total_size = len(set(gems))
    left, right = 0, 0

    cur_dict = {gems[left]: 1}
    answer = [0, len(gems)-1]
    min_length = sys.maxsize

    while left < len(gems) and right < len(gems):
        while left < len(gems) and len(cur_dict) >= total_size:  # 이미 길이가 충분한 경우
            if min_length > right - left:  # 역대 최소 길이라면
                answer = [left, right]
                min_length = min(min_length, right - left)

            if cur_dict[gems[left]] == 1: # 딱 하나 남았다면 통째로 삭제한다
                del cur_dict[gems[left]]
            else: # 그게 아니라면 개수만 하나 깐다
                cur_dict[gems[left]] -= 1

            left += 1


        while right < len(gems) and len(cur_dict) < total_size:  # 부족하다면
            right += 1
            if right == len(gems):
                break
            if gems[right] not in cur_dict:
                cur_dict[gems[right]] = 1
            else:
                cur_dict[gems[right]] += 1

    return [answer[0]+1, answer[1]+1]


print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]), [3, 7])

처음에는 dictinoary 대신에 set을 썼다가 시간 초과가 났다. 투포인터라는 것을 바로 캐치한 것은 잘했다. 인덱스를 초과하는 예외가 잘 발생하니 조심해서 풀어야 한다.

다른 사람 풀이

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]