https://school.programmers.co.kr/learn/courses/14760/lessons/125468
본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.
어느 날 스트레스를 풀기 위해 보석 매장에 쇼핑을 하러 간 어피치는 이전처럼 진열대의 특정 범위의 보석을 모두 구매하되 특별히 아래 목적을 달성하고 싶었습니다.
진열된 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾아서 구매하기
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems가 매개변수로 주어집니다. 이때 모든 보석을 하나 이상 포함하는 가장 짧은 구간을 찾아서 return 하도록 solution 함수를 완성해주세요.
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.
본 문제는 투 포인터를 사용해서 구현했다.
추후 보완 예정
import collections
def solution(gems):
answer = []
hash = collections.defaultdict(int)
length = len(set(gems)) # 중복되지 않는 보석의 종류 개수
left = 0 # left pointer의 첫 시작점
max_length = 100000 # 최대 길이는 보석의 개수로 설정
for right in range(len(gems)):
hash[gems[right]] += 1 # 보석(키 값)에 대한 개수(value)를 증가시킴
while(len(hash) == length): # hash 길이가 (=key값의 개수가) length개 일때만 실행
if right-left+1 < max_length: # max_length 갱신이 가능한 경우, 새로운 값으로 바꿔줌
max_length = right-left+1 # 최대 길이와 이때의 구간 저장
answer = [left+1, right+1]
hash[gems[left]] -= 1 # left를 오른쪽으로 한칸씩 옮기면서 이동이 가능한지 파악
if hash[gems[left]] == 0: # 해당 키 값의 value가 0이면, 해당 키를 삭제
del hash[gems[left]]
left += 1 # 키가 삭제되지 않았다면, left를 오른쪽으로 이동시킴
return answer
실행 결과
- 정확성 테스트 및 효율성 테스트