[Python] 프로그래머스. 2020 카카오 인턴 - 보석 쇼핑 (Level 3)

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

코딩테스트 연습 - 보석 쇼핑

실제 테스트할 때 효율성을 끝까지 해결 못 했던 문제.

처음 접근할 때는 '이분탐색으로 window 사이즈 탐색' + '해당 window size가 조건을 충족하는지 확인'하는 방식으로 풀었는데,

다시 풀면서 접근해보니 리스트 슬라이싱을 쓰면 시간초과가 반드시 등장했다.

 

정답은 투 포인터를 활용한 탐색.

 

 

	from collections import defaultdict
	import heapq
	def solution(gems):
	start, end = 0, 1
	gem_loc = defaultdict(int)
	gem_target = len(set(gems))
	# 가장 길이가 짧은 좌표 저장을 위해 heap 자료구조 사용.
	answer = []
	# 첫 번째 보석의 위치.
	gem_loc[gems[start]] = 1
	while start < len(gems):
	if len(gem_loc) == gem_target:
	heapq.heappush(answer, (end - start + 1, start, end))
	# start를 오른쪽으로 이동
	# 현재 start 위치의 값을 1 낮춘다.
	# 0이 될 경우, 해당 보석이 범위 내에 없게 된다.
	gem_loc[gems[start]] -= 1
	if gem_loc[gems[start]] == 0:
	# 보석 삭제
	del gem_loc[gems[start]]
	start += 1
	else:
	## 더 이상 포인터 이동이 불가능.
	if end == len(gems):
	break
	gem_loc[gems[end]] += 1
	end += 1
	return [answer[0][1]+1, answer[0][2]]

view raw [프로그래머스] 보석 쇼핑.py hosted with ❤ by GitHub