카카오2020인턴-보석쇼핑

소요시간: 40분

 

나의 정답코드

import collections
def solution(gems):
    gemNum=len(set(gems))
    lt=0
    rt=0
    selected = collections.defaultdict(int)
    answer=[0,1e9]
    selected[gems[lt]]+=1
    while True:
        if len(selected)<gemNum:
            if rt==len(gems)-1:
                break
            else:
                rt+=1
                selected[gems[rt]]+=1
        else:
            if rt-lt+1<answer[1]-answer[0]+1: 
                answer=[lt+1,rt+1]
            if rt-lt+1==answer[1]-answer[0]+1 and lt<answer[0]:
                answer=[lt+1,rt+1]
                
            selected[gems[lt]]-=1
            if selected[gems[lt]]<=0:
                selected.pop(gems[lt],None)
            lt+=1
            

            
    return answer

디폴트딕셔너리를 이용하여 보석의 수를 카운트하고 0개가되면 삭제했다. 디폴트딕셔너리를 사용하면 int타입으로 설정시 기본이0 이다. 

딕셔너리에 없는 키라하더라도 +1을 해주면 자동으로 생성도 해준다.

투포인터를 이용하여 lt=0, rt=0에서 시작해서 모든 보석이 포함된다면 lt를 오른쪽으로 옮겨 좁혀가고 보석이 부족하다면 rt를 오른쪽으로 옮겨 많은 보석을 포함하게 했다. rt가 끝까지 간 상태이고 보석의 수가 부족하다면 lt를 아무리 오른쪽으로 옮겨도 부족하기에 break해준다. 

답을 구할 때는 길이, 시작점 을 순서대로 비교하여 구해준다.

 

 

정확도테스트는 통과 하였지만 효율성테스트는 통과를 통한 코드

import collections
def solution(gems):
    gemNum=len(set(gems))
    ans=[]
    lt=0
    rt=0
    while True:
        selected = set(gems[lt:rt+1])
        if len(selected)<gemNum:
            if rt==len(gems)-1:
                break
            else:
                rt+=1
        else:
            ans.append((rt-lt+1,lt,rt))
            lt+=1
    ans.sort(key = lambda x: (x[0],x[1]))
    answer= [ans[0][1]+1,ans[0][2]+1]

리스트 슬라이스는 복잡도가 b-a이다 [a:b]

이부분에서 시간초과가 나온 것 같다. 

 

 

 

정답 예시코드

import collections
def solutions(gems):
	answer: [0,0]
    sH= collections.defaultdict(int)
    k = len(set(gems))
    lt = 0
    maxL= 1000000
    for rt in range(len(gems)):
    sH[gems[rt]+=1
    while(len(sH)==k):
    	if re-lt+1 <maxL:
        	maxL = rt -lt +1
        	answer:=[lt+1,rt+1]
        if sH[gems[lt]] == 0:
        	del sH[gems[lt]]
        lt+=1
        
	return answer

투포인터시 상황에 따라 하나의 포인터는 for문으로 처리하면 더욱 간결하게 구현할 수 있다.