[Python] 보석쇼핑

https://programmers.co.kr/learn/courses/30/lessons/67258?language=python3

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

투 포인터 알고리즘을 사용!

 

1. 먼저 배열 인덱스를 저장하는 start 변수와 end 변수를 선언

2. 배열의 start 와 end 구간이 “모든 종류의 보석을 포함하는 구간”이 될 때 까지 end 인덱스를 증가

 

진열대 번호 : 1 2 3 4 5 6 7 8인덱스 번호 : 0 1 2 3 4 5 6 7보석의 종류 : D R R D D E S D

start = 0 end = 0 구간안에있는 보석 : [ ]
start = 0 end = 1 구간안에있는 보석 : [D]
start = 0 end = 2 구간안에있는 보석 : [D, R]
start = 0 end = 3 구간안에있는 보석 : [D, R, R]
start = 0 end = 4 구간안에있는 보석 : [D, R, R, D]
start = 0 end = 5 구간안에있는 보석 : [D, R, R, D, D]
start = 0 end = 6 구간안에있는 보석 : [D, R, R, D, D, E]
start = 0 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S]

 

 

3. “구간 중 가장 짧은 구간” 을 구해야 하기 때문에 start 인덱스를 하나씩 증가시켜보며 구간의 길이를 줄여본다. 줄어든 구간이 “모든 종류의 보석을 적어도 1개 이상 포함” 한다는 조건을 만족시키면 현재start , end 를 저장하고, 조건이 만족되지 않을 때까지 구간의 길이를 줄임

진열대 번호 : 1 2 3 4 5 6 7 8
인덱스 번호 : 0 1 2 3 4 5 6 7
보석의 종류 : D R R D D E S D
start = 0 end = 0 구간안에있는 보석 : []
start = 0 end = 1 구간안에있는 보석 : [D]
start = 0 end = 2 구간안에있는 보석 : [D, R]
start = 0 end = 3 구간안에있는 보석 : [D, R, R]
start = 0 end = 4 구간안에있는 보석 : [D, R, R, D]
start = 0 end = 5 구간안에있는 보석 : [D, R, R, D, D]
start = 0 end = 6 구간안에있는 보석 : [D, R, R, D, D, E]
start = 0 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S]조건만족: O
start = 1 end = 7 구간안에있는 보석 : [D, R, R, D, D, E, S]조건만족: O
start = 2 end = 7 구간안에있는 보석 : [R, R, D, D, E, S]조건만족: O
start = 3 end = 7 구간안에있는 보석 : [R, D, D, E, S]조건만족: O
start = 4 end = 7 구간안에있는 보석 : [D, D, E, S] 조건만족: X

 

4. 현재 구간이 조건을 만족시키지 않는다면 다시 end 인덱스를 증가시키면서 구간을 탐색한다.

5. 위 과정을 반복한다. 

 

6. 구간을 전부 탐색했다면 탐색을 종료하고 조건을 만족하는 구간들 중에 길이가 가장 짧은 구간의 start , end 를 리턴한다.

 

파이썬 코드

from collections import defaultdict


def solution(gems):
    answer = [0,0]
    candidates = []
    start, end = 0, 0
    
    # set함수를 이용하여 보석의 종류 확인
    # set 생성시간복잡도 O(len(gems))
    gems_len, gems_kind = len(gems), len(set(gems))
    # defaultdict(int)와 동일하게 동작; 0을 리턴
    # defualt key 값이 0으로 저장
    gems_dict = defaultdict(lambda : 0)
                                        
    while True:
        kind = len(gems_dict)
        if start == gems_len:# 탐색 종료
            break
        if kind == gems_kind:
            # 후보 인덱스 페어를 저장
            candidates.append((start, end))
            gems_dict[gems[start]] -= 1
            if gems_dict[gems[start]] == 0:
                del gems_dict[gems[start]]
            start += 1
            continue
        if end == gems_len: 
            break
        if kind != gems_kind:
            gems_dict[gems[end]] += 1
            end += 1
            continue
            
            
    length = float('inf') # 양의 무한대로 설정
    for s, e in candidates:
        if length > e-s:
            length = e-s
            answer[0] = s + 1
            answer[1] = e
    return answer