[프로그래머스] 보석 쇼핑(python 파이썬)

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

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

모든 보석을 포함하는 최소 구간을 구하는 문제이다.

 

우선 모든 구간이기 때문에 안될걸 알지만 생각나는 방법이 없어서

nC2를 이용하여 모든 구간을 구하여 풀었다.

 

gems 배열의 크기는 1 이상 100,000 이하이다 

100000C2를 하면 50억(?)정도 나온다...

 

조합으로 푼 코드

import math

min_result = list()
min_range = math.inf


def solution(gems):
    gems_kind = set(gems)

    if len(gems_kind) == 1:
        return [1, 1]

    visited = [False] * len(gems)
    combination(visited, 0, 0, len(gems_kind), gems)

    answer = list()
    while min_result:
        x, y = min_result.pop()
        if y - x == min_range:
            answer.append([x + 1, y + 1])
    answer.sort()

    return answer[0]


def combination(visited: list, s, depth, gems_kind, gems):
    global min_range
    if depth == 2:
        s_e = list()
        for i in range(len(visited)):
            if visited[i]:
                s_e.append(i)
        if len(set(gems[s_e[0]: s_e[1] + 1])) == gems_kind:
            if min_range >= s_e[1] - s_e[0]:
                min_range = s_e[1] - s_e[0]
                min_result.append([s_e[0], s_e[1]])
        return

    for i in range(s, len(visited)):
        if visited[i]:
            continue

        visited[i] = True
        combination(visited, i, depth + 1, gems_kind, gems)
        visited[i] = False

 

 

해결 방법이 떠오르지 않아 답을 봤다.

2개의 포인터를 사용하고

포인터를 움직이면서

포인터의 사이에 사전을 이용하여 사전의 길이와 보석를 확인하며 푼다.

 

정식 문제 해설

풀이를 보니 어려운문제는 아니지만 처음 접하는 유형이었다..

 

def solution(gems):
    gems_kind = set(gems)

    if len(gems_kind) == 1:
        return [1, 1]

    lp, rp = 0, 0
    answer = [1, len(gems)]
    gems_dict = dict()
    gems_dict[gems[0]] = 1
    while lp < len(gems) and rp < len(gems):
        if len(gems_dict) == len(gems_kind):
            if answer[1] - answer[0] > rp - lp:
                answer = [lp+1, rp+1]
            if gems_dict[gems[lp]] != 1:
                gems_dict[gems[lp]] -= 1
            else:
                del gems_dict[gems[lp]]
            lp += 1
        else:
            rp += 1
            if rp >= len(gems):
                break
            if not gems[rp] in gems_dict:
                gems_dict[gems[rp]] = 1
            else:
                gems_dict[gems[rp]] += 1
    return answer