[프로그래머스/Python] Level 3_보석 쇼핑

📌문제 유형

2020 카카오 인턴십

 

📌문제

프로그래머스

 

 

📌나의 문제풀이

- 정답 11. 나머지 시간초과

• product를 활용해서 모든 경우의 수 - 그중 가장 작은 수 구함

from itertools import product

def solution(gems):
    answer = []
    result_range = 100001
    
    # 모든 종류 보석
    gems_type = list(set(gems))
    
    # 종류별 숫자 세기
    gems_dict = {}
    for gem in gems_type:
        gems_dict[gem] = []
    
    # 전체 위치 저장
    for i in range(len(gems)):
        gems_dict[gems[i]].append(i)
    
    # 모든 경우의 수 선정 -> 오름 차순 -> 범위, 위치 저장
    all_p = list(product(*gems_dict.values()))
    for p in all_p:
        scale = [min(p)+1, max(p)+1]
        range_ = scale[1] - scale[0]
        if range_ < result_range:
            result_range = range_
            answer = scale
    
    return answer

 

- 정답 73.3. 나머지 시간초과

• dict로 시간 문제 줄임
• 모두 순회하면서 위치값 갱신 -> 최소값 찾기

def solution(gems):
    answer = []
    result_range = 100001
    
    # gems 종류
    gems_type = list(set(gems))
    
    # 저장소 선언
    gem_value = dict()
    for gem in gems_type:
        gem_value[gem] = -1
    
    # 모두 순회하면서 확인
    tmp = []
    for i in range(len(gems)):
        gem_value[gems[i]] = i
        if -1 not in gem_value.values():
            tmp = [min(gem_value.values()) + 1, max(gem_value.values()) + 1]
            range_ = tmp[1] - tmp[0]
            if range_ < result_range:
                result_range = range_
                answer = tmp
    return answer

 

- 정답 77.8. 나머지 시간초과

• 저장소 선언 줄임

def solution(gems):
    answer = []
    result_range = 100001
    
    # gems 종류
    gems_type = list(set(gems))
    
    # 저장소 선언
    gem_value = dict()
    
    # 모두 순회하면서 확인
    tmp = []
    for i in range(len(gems)):
        gem_value[gems[i]] = i
        
        if len(gem_value) == len(gems_type):
            tmp = [min(gem_value.values()) + 1, max(gem_value.values()) + 1]
            range_ = tmp[1] - tmp[0]
            if range_ < result_range:
                result_range = range_
                answer = tmp
    return answer

 

📌다른사람의 문제풀이

- 투 포인터로 접근

[프로그래머스] 보석 쇼핑 / Python

def solution(gems):
    answer = [] 
    shortest = len(gems)+1 # 현재 최단 구간 길이

    start_p = 0 # 구간의 시작점
    end_p = 0 # 구간의 끝 점 (보석을 체크하는 기준점)

    check_len = len(set(gems)) # 보석의 총 종류 수
    contained = {} # 현재 구간에 포함된 보석들(종류: 갯수)

    while end_p < len(gems): # 구간의 끝 점이 gems의 길이보다 작을 동안

        if gems[end_p] not in contained: # 현재 끝 점의 보석이 contained에 없다면(이 종류가 처음 발견되었다면)
            contained[gems[end_p]] = 1 # dictionary에 추가
        else:
            contained[gems[end_p]] += 1 # 이미 있으면 dictionary에 +1
            
        end_p += 1 # 끝 점 증가

        if len(contained) == check_len: # 현재 구간 내 보석의 종류의 갯수가 전체 종류의 갯수와 같다면 (현재 구간내 모든 종류가 다 있다면)
            while start_p < end_p: # start_p 가 end_p 보다 같을 때까지 증가
                if contained[gems[start_p]] > 1: # start_p에 해당하는 보석이 구간 내에 하나 이상 있다면
                    contained[gems[start_p]] -= 1 # 구간 내 보석 하나 감소(start_p 의 보석 뺄거니까)
                    start_p += 1 # start_p 증가
                    
                elif shortest > end_p - start_p: # 기존의 구간 최단거리보다 현재의 구간거리가 더 짧다면
                    shortest = end_p - start_p
                    answer = [start_p+1, end_p] # answer와 최단거리 갱신
                    break
                    
                else:
                    break


    return answer