[PG/Python] 보석 쇼핑

📌 문제

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

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

 

📌 문제 접근 방법

1. 맨 처음에 짠 코드는 각 보석들의 인덱스를 딕셔너리에 저장한 후, 보석마다 가장 뒤에 있는 인덱스를 start에 담아주고 가장 앞에 있는 인덱스를 end에 담아줬다.
2. 그 후, start에서 가장 작은 값과 end에서 가장 큰 값을 범위로 설정하면 최소의 길이로 모든 보석을 포함하는 구간을 찾을 수 있다. -> 하지만 짧은 구간이 여러 개일 경우 시작 진열대 번호가 가장 작아야 한다는 조건을 만족시키지 못한다.
3. 그래서 코드를 아예 갈아엎고 이분탐색을 사용해서 풀이하였다.
4. start는 0, end는 보석 종류의 개수로 초기값을 설정하고, end를 하나씩 늘리면서 탐색하다가 start~end 구간 내의 보석 종류의 개수가 전체 보석 종류의 개수와 같다면 이를 able에 넣고 start를 증가시킨다.
5. 반복문이 끝나고 able에 저장된 범위를 길이를 기준으로 sort한 후, 0번째를 리턴한다. (문제에서는 1부터 시작하므로 1씩 더해야 한다.)

 

📌 코드

from collections import defaultdict

def solution(gems):
    if len(set(gems)) == 1:
        return [1, 1]
    
    locations = defaultdict(list)
    for i in range(len(gems)):
        locations[gems[i]].append(i)
    
    start = []
    end = []
    for location in locations.values():
        start.append(max(location))
        end.append(min(location))
        
    return [min(start)+1, max(end)+1]

 

def solution(gems):
    n = len(gems)
    n_set = len(set(gems))
    
    include = {}
    for gem in set(gems):
        include[gem] = 0
    
    start = 0
    end = n_set - 1
    kind = 0
    for i in range(start, end+1):
        if include[gems[i]] == 0:
            kind += 1
        include[gems[i]] += 1
    
    able = []
    
    while True:
        if kind == n_set:
            able.append([start, end])
            if include[gems[start]] == 1:
                kind -= 1
            include[gems[start]] -= 1
            
            start += 1
            if start > n - n_set:
                break
        else:
            end += 1
            if end == n:
                break
                
            if include[gems[end]] == 0:
                kind += 1
            include[gems[end]] += 1
    
    able.sort(key=lambda x: x[1]-x[0])
    return [able[0][0]+1, able[0][1]+1]