[프로그래머스] 보석 쇼핑

 

정확성 테스트/효율성 테스트

투 포인터 안한지 하도 오래되서 그런지 엄청 어려웠습니다.. 투 포인터인 것은 바로 알았는데 투 포인터를 어떻게 이용해야 하는지 감 잡기가 어려운 문제였던 것 같습니다.

0. 무조건 투 포인터 문제일 것
0.1 DP로 풀려면 10만*10만의 배열이 필요할 것
0.2 그냥 탐색을 하려면 엄청 큰 시간복잡도
1. gems를 Set화한 크기를 무조건 알아야 함,
2. 방문과 방문횟수에 사용할 딕셔너리(맵)가 필요함, 딕셔너리를 채워나가며 코드를 진행
2.1 방문하지 않은 보석을 방문하면 딕셔너리의 크기들을 더해주면 1+2+3+4...n n(n+1)/2임 n은 set화 했던 크기 (취소)
2.2 굳이 저럴 필요 없이 len으로 비교해줘도 가능할 듯
2.3 두 방법 모두 딕셔너리에서 del을 통한 크기 비교 및 방문  초기화를 해줘야 할 것
3. 파이썬의 try except를 통해 딕셔너리의 크기를 늘리고 방문했던 딕셔너리는 방문 횟수를 더해주는 방식
4. R의 값은 딕셔너리의 크기와 set화했던 크기가 같을때까지는 무한 반복
5. L의 값은 r값이 증가하며 딕셔너리의 크기와 set의 크기가 같아졌을 때,딕셔너리의 키값으로 배열의 l번째 값의 방문횟수를 -1== 0이 되면del시키켜줌
5.1 위 조건을 만족한 경우 구간의 길이 r-l,l,r 을 구할 수 있음, 앞으로 쭉 비교해주면 최솟값을 얻을 수 있다
6. 모든 탐색이 종료된 후 얻은 최솟값을 리턴

일단 이렇게 적어놓고 문제를 풀기 시작했습니다.

기본적으로 필요한 값들은 정답을 저장할 변수들, 포인터 2개, 방문과 방문횟수를 저장할 딕셔너리 1개, gems의 중복되지 않는 원소의 개수를 값으로 갖는 변수라고 생각했습니다.

length=len(set(gems))
vi=defaultdict(int)
answer=(100001,0,0)
start=end=0

 

최대 100000개이므로 구간의 길이는 결코 100001보다 클 수 없습니다. 이 때 일반적인 딕셔너리 말고 collections 모듈의 defaultdict을 사용해주었습니다. C++의 map과 거의 비슷하게 파이썬에서도 쓸 수 있게 해주는 것 같습니다. 특정 테스트 케이스의 경우 일반 딕셔너리와 속도차이가 거의 2배나 빠릅니다. 

일단 length(중복되지 않는 gems의 원소 개수)와 vi(방문한 원소를 키, 방문한 횟수를 밸류로 갖는 딕셔너리)의 길이가 같은 경우까지 end를 계속 증가시켜 주며 gems[end]를 키로 사용해서 vi에 넣어주었습니다.

while len(vi)<length:
	vi[gems[end]]+=1
	end+=1

만약 위의 두 값이 같아졌다면 start부터 end사이에는 gems의 중복되지 않는 원소들이 모두 들어있다는 말이 되죠, 그럼 모두 들어있지 않은 상태가 될 때 까지 start를 증가시켜줍니다. 그리고 증가시키기 전의 gems[start]를 키로 사용해 방문횟수를 -1시켜줍니다. 방문횟수가 0이 되었다면 그 원소는 더이상 vi에 존재하지 않는다는 얘기이므로 del을 통해 방문한적 없는 것으로 바꿔줍니다.

while len(vi)==length:                
	vi[gems[start]]-=1
	if vi[gems[start]]==0:
		del vi[gems[start]]
		start+=1
		break
	start+=1

그리고 정답을 비교해주면 됩니다.

최종 코드입니다.

from collections import defaultdict

def solution(gems):
    length=len(set(gems))
    vi=defaultdict(int)
    answer=(100001,0,0)
    start=end=0
    try:
        while:
            while len(vi)<length:
                vi[gems[end]]+=1
                end+=1
            while len(vi)==length:                
                vi[gems[start]]-=1
                if vi[gems[start]]==0:
                    del vi[gems[start]]
                    start+=1
                    break
                start+=1
            answer=min(answer,(end-start+1,start,end))
    except:
        return answer[1:]

종료 조건은 try와 except를 사용했습니다. end의 값이 계속 증가하여 인덱스를 벗어난 상태에서 vi의 키로 사용하려 할때 에러가 발생합니다. 그 떈 이미 gems의 끝까지 다 돌아본 상태이므로 그냥 return 해주면 됩니다.