[Algorithm]Programmers:Python宝石購入

[質問へ]https://programmers.co.kr/learn/courses/30/lessons/67258

📌問題の説明

開発者出身で世界一の金持ちになったApacheは、ストレスを解消するために実店舗で買い物をすることが多い.
魚桃は買い物をするとき、売り場の棚の特定の範囲のものを一掃することに慣れています.
ある日、ストレスを解消するためにジュエリーショップに買い物に行ったフィッチは、以前のように棚のすべての特定の範囲のジュエリーを購入し、特に以下の目的を達成したいと思っていました.
少なくとも1つ以上陳列されている宝石を含む最短区間を探して購入します.
例えば、以下に、8種類の宝石(RUBY、DIA、EMERALD、SAPPHIRE)を示す例を示す.

棚の3番から7番まで5つの宝石を購入し、すべての種類の宝石は少なくとも1つ以上含まれています.
棚の3、4、6、7番の宝石だけを購入すると、真ん中に特定の区間(5番)が欠け、魚の皮魚の買い物習慣に合わない.
パラメータは、ショーケース番号順に宝石名を格納する配列gemsです.この場合、1つ以上の宝石を含む最短区間を見つけて戻ります.
最短区間の開始棚番号と終了棚番号を順番にシーケンスに入れて返し、複数の最短区間がある場合は開始棚番号の最小区間を返します.
せいげんじょうけん

gems配列の大きさは1または10万以下である.

gemsアレイの各要素はショーケースにリストされた宝石を表す.

gems配列では、1番ショーケースから、ショーケース番号順に宝石名を格納する.

gems配列の各要素は、1または10未満の長さのアルファベット大文字からなる文字列である.

💡 問題を解く

正確性も有効性も満たさなければ正解の問題を処理できない...!
(=データ構造の重要性を理解)
gems配列のサイズは1以上100000以下であるため,二重繰返し文は効率要件を満たすことができないことは明らかである.
二重複文で解決できなければ、「二重ポインタ」で解決するという.
そのため、この問題にも起点、終点の2つのポインタが設けられて答えを探しています.
step 1)
変数の宣言

左:始点

右:終了点

start:最小区間の起点

length:最小セグメント長

step 2)
問題を解決する手順は次のとおりです.

開窓値を左右に調整します.(gems[left:right+1])

スライス結果に全種類が含まれているか.

全ての種類を含む場合、最小のセグメント長であるか否かを比較し、長さ、start値を最新化する.その後、左の値が1増加します.

全ての種類が含まれていなければ区間の長さを広げる必要があるので、正確な値を1つ増やします.

デュアルポインタはgems配列の特定の値を指すインデックスです.
したがって、2つの値がgemsの範囲を超えた場合、ナビゲーションが完了します.
コードは次のとおりです.
効率失敗-タイムアウト

def solution(gems):
    candidates = set(gems)
    if len(candidates) == 1:
        return [1, 1]
    elif len(candidates) == len(gems):
        return [1, len(gems)]
    else:
        left, right = 0, 0
        start = int(1e9)
        length = int(1e9)
        while left < len(gems) - len(candidates) and right < len(gems):
            if len(set(gems[left:right+1])) == len(candidates):
                if right - left < length:
                    length, start = right - left, left
                left += 1
            else:
                right += 1
        return [start+1, start+length+1]

正解を送信すると、効率部分がタイムアウトします.
いずれにせよ、グライダー作業は時間の複雑さを増しているようだ.
※スリップの時間的複雑さは、スリップの要素数に比例します.
ex) li[a:b] → O(b-a)
問題を解決するために、ディクソン資料構造を使用しました.
以前は希望区間を比較していましたが、ディックの分類法を利用して、資料を「種類」(key)-「個数」(value)の形で保存することができ、簡単に個数を把握するだけです.
資料構造の違いのみが存在し,順序は同じである.
鍵(keys)の長さ(len)を使用して、すべての資料が含まれているかどうかを確認します.そうでなければright+1です.
すべての資料が含まれている場合はleft+1を行い、最小のセグメント長を求めるだけでよい.
コードは次のとおりです.
正解

def solution(gems):
    kinds = len(set(gems))
    gems_dict = {gems[0]:1}
    answer = [0, len(gems) - 1]
    left , right = 0, 0

    while(left < len(gems) and right < len(gems)):
        if len(gems_dict) == kinds:
            if right - left < answer[1] - answer[0]:
                answer = [left, right]
            if gems_dict[gems[left]] == 1:
                del gems_dict[gems[left]]
            else:
                gems_dict[gems[left]] -= 1
            left += 1
        else:
            right += 1
            if right == len(gems):
                break
            if gems[right] in gems_dict.keys():
                gems_dict[gems[right]] += 1
            else:
                gems_dict[gems[right]] = 1

    return [answer[0]+1, answer[1]+1]