-
[투 포인터] 보석 쇼핑 (파이썬)코딩 테스트/프로그래머스 2023. 4. 20. 19:52
문제 설명
https://school.programmers.co.kr/learn/courses/30/lessons/67258
문제 풀이
- 투 포인터를 이용해서
- 모든 보석 종류를 수집하지 못했다면 end +1
- 모든 보석 종류를 수집해서 end까지의 최소 길이 구하기 위해 start+1
- 특정 보석의 갯수는 딕셔너리를 이용해서 체크
- 모든 보석 종류를 수집했는지는 r이라는 변수를 두고 수집 할 보석 갯수 nn 가 비교해서 알아냄
- r==nn 이면 모든 보석을 수집한 것이므로 최소 길이를 구하기 위해 start를 +1 씩 해주면서 체크
- 이 때 start가 거쳐간 것들의 보석 갯수는 -1 을 해주다가 특정 보석의 갯수가 0이 된다면 그곳이 최소 길이의 첫 시작이 된다.
- 위의 과정이 끝났다고 결과값이 나오는 것이 아니므로 이 후 탐방을 계속 해주면서 체크
소스 코드
# gems len 100,000 이하 def solution(gems): answer = [0,len(gems)] result = len(gems) w = list(set(gems)) # 보석 종류 알기 위해 집합 cnt = dict() # 탐방 시 보석 갯수 체크 for i,ddd in enumerate(w): cnt[ddd]=0 n = len(gems) # 탐방 할 보석 전체 길이 nn = len(w) # 주어진 보석 갯수 if(nn==1): # 보석 한 종류면 그냥 끝 return [1,1] start,end =0,0 #투 포인터 cnt[gems[end]]=1 r=1 #보석 다 모았는지 체크 용도 while(start<n and end<n): if(r==nn): if (end-start<result): answer=[start,end] result=end-start else: cnt[gems[start]]-=1 if cnt[gems[start]]==0: r-=1 start+=1 else: end+=1 if(end==n): break cnt[gems[end]]+=1 if(cnt[gems[end]])==1: r+=1 return [answer[0]+1,answer[1]+1] print(solution(["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]))
ㅡ
'코딩 테스트 > 프로그래머스' 카테고리의 다른 글
[힙] 디스크 컨트롤러 (파이썬) (0) 2023.04.21 [이분 탐색] 징검다리 건너기 (파이썬) (0) 2023.04.20 [파이썬] 기지국 설치 (0) 2023.04.17 [2021 카카오 블라인드] 합승 택시 요금 (파이썬) (0) 2023.04.17 [탐색] 여행 경로 (python) (1) 2023.04.16