[Python/프로그래머스]보석쇼핑_(KaKao)_[투포인터]

 

 

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

프로그래머스

 

 

 

🐾 20221008

 

 

 

 

 

쉬워보여서 그냥 구현으로 만들어봤다. 

def solution(gems):
    answer = []
    gem = set(gems)
    num = len(gem)
    for i in range(len(gems) - num+1) :
        tmp = set()
        for j in range(i,len(gems)) :
            tmp.add(gems[j])
            if len(tmp) == num : 
                answer.append([i+1,j+1])
                break
    answer.sort(key = lambda x : (x[1]-x[0],x[0]))
    return answer[0]

 

 

 

정확성은 잘 나오지만 효율성에서 전부 시간초과가 나왔다. 😢

 

 

 

 

 

 

 

 

 

 

( 딕셔러니를 이용한 )

투포인터를 사용해서 풀어야한다!!

 

 

 

 

gems를 s,e 포인터를 이용하여 탐색한다. 

s,e까지의 값들을 딕셔너리에 넣어가면서 개수가 작으면 e를 증가시키고 

같을 경우 answer을 갱신하고 s를 증가시킨다. 

 

s,e값들 중 하나라도  gems를 벗어나면 끝난다. 

 

0-index이므로 답을 1씩 증가해준다. 

 

 

<정답 코드> : 

def solution(gems):
    n = len(gems)
    # 최대길이로 초기화 
    answer = [0,n-1]
    kind = len(set(gems))
    dic = {gems[0]:1}
    s,e = 0,0
    
    while s<n and e<n :
    	# 종류가 부족하면 
        if len(dic) < kind :
            # 오른쪽을 한칸 움직임 
            e+=1 
            # 만약 끝이라면 while문을 끝냄 
            if e ==n : break
            # 움직인 오른쪽의 보석을 dict에 넣음 
            dic[gems[e]] = dic.get(gems[e],0) + 1 
        else :
        	# 더 작은 구간으로 갱신 
            if (e-s+1) < (answer[1]-answer[0]+1) :
                answer = [s,e]
            # start를 오른쪽으로 한칸 움직일거라서
            # dict에서 빼줌 
            if dic[gems[s]] == 1 :
                del dic[gems[s]]
            else : dic[gems[s]] -=1 
            s+=1 
            
    answer[0] +=1 
    answer[1] += 1 
    return answer

 

 

 

 

배운 것 :

 

dictionary에서 get을 이용하면 값을 불러올 수 있다. 

첫번째 인수에는 키값을 넣고 두번째 인수는 필수는 아니다. 

두번째 인수는 (만약 해당 키 값에 해당하는 Value가 없다면 이를 대신해서 나올 값을 넣는다.)

 

만약 두번째 인수를 넣지않았는데 첫번째 인수로 넣은 키가 딕셔너리에 없다면 None를 반환한다. 

 

 

 

 

 

복습하면서 잊어먹은 것 : 

end를 1증가할 때 이 증가한 값이 범위를 넘어버린다면 break를 해야한다.

이거를 까먹어서 틀렸다.🥴

 

if end == n : break

 

 

 

 

복습 코드 : 

def solution(gems):
    dic = {}
    n = len(gems)
    answer = [0,n-1]
    length = len(set(gems))
    dic[gems[0]] = 1
    i,j = 0,0 
    while i < n and j < n :
        if len(dic)>=length :
            if (answer[1]-answer[0]) > (j-i) :
                answer = [i,j]
            if dic[gems[i]] > 1 : dic[gems[i]] -=1 
            else : del dic[gems[i]]
            i+=1 
        else :
            j+=1 
            if j == n : break 
            dic[gems[j]] =  dic.get(gems[j],0)+1 
    answer[0] +=1 
    answer[1] +=1
    return answer

 

 

 

 

 

 

참고 블로그 : 

https://jennnn.tistory.com/79

[프로그래머스] 보석 쇼핑 / python 파이썬 / 2020 카카오 인턴십 코테