異なるアルゴリズムタイプのエクスポート問題:Griddy

💻 4.作成できない金額

難易度🖤🤍🤍 | プール時間30分|制限時間1秒|メモリ制限128 MB|2019 KACA新公開発行https://programmers.co.kr/learn/courses/30/lessons/42891

📌2021、01/07コード作成

(正確性テストに合格したコードのみ)

def solution(food_times, k):
    answer = 0 # 인덱스 역할을 한다

    # 다음 while 문에서 무한 루프에 빠질 가능성 있다...
    # 무한 루프에 빠질 가능성, 즉, 모든 음식을 다 먹는 데 걸리는 시간보다 k초가 크면 -1
    if sum(food_times) <= k:
        return -1

    while k > 0:
        # 음식이 남아 있음
        if food_times[answer] > 0:
            food_times[answer] -= 1
            k -= 1
            answer += 1

        # 음식이 남아 있지 않음
        else:
            answer += 1

        # 인덱스 범위 초과 시 적절한 범위로 초기화
        if answer >= len(food_times):
            answer -= len(food_times)

    # k초 동안 먹고 다음에 먹을 인덱스는 현재 answer에 저장되어 있음
    # 정상화 후 먹을 음식: food_times[answer] 이므로 유효성을 검증해야한다
    # 무한 루프에 빠질 가능성 배제한 뒤의 검증
    while food_times[answer] <= 0:
        answer += 1
        # 인덱스 범위 초과 시 적절한 범위로 초기화
        if answer >= len(food_times):
            answer -= len(food_times)

    return (answer+1) #answer는 인덱스이므로 +1

print(solution([1, 2, 3], 8))

効率テストはすべてNagary...効率はいったいどのように通過したのだろうか.
(効率テストで作成し破壊するためのコード)

import heapq

def solution(food_times, k):
    # 예외: return -1
    if sum(food_times) <= k:
        return -1

    answer = 0

    # cycle, remain
    cycle = k // len(food_times)
    remain = k % len(food_times)
    # food_times 내에서 최소 시간
    min_time = min(food_times)

    # CASE1: 접시를 비울 수 있는 음식이 없을 때
    if min_time > cycle:
        # answer = (remain + 1)
        answer = remain + 1
        return answer

    # CASE2: 접시를 비울 수 있는 음식이 있을 경우
    else:
        # 최소 힙을 만든다
        heap = []
        # food_times의 원소들을 (value, idx)꼴로 최소힙에 옮겨담는다
        for i in range(len(food_times)):
            heapq.heappush(heap, (food_times[i], i))

        # 최소힙에서 cycle보다 작거나 같은 원소를 모두 remove
        # cycle을 돈 뒤 접시가 비워지는 원소들을 제거해주는 것
        while heap[0][0] <= cycle:
            heapq.heappop(heap)

        # 최소힙에 남아 있는 원소들 중 remain번째의 인덱스+1이 answer
        # 최소힙에 남아 있는 원소들의 idx 기준으로 오름차순으로 정렬
        rem_idx = [x[1] for x in heap]
        rem_idx.sort()
        print("rem_idx:", rem_idx)

        # CASE1
        if remain < len(rem_idx):
            print('case1')
            answer = rem_idx[remain] + 1
        # CASE2
        else:
            print('case2')
            # 다시 최소 힙 사용하기
            heap.clear()
            # 최소 힙에 food_times와 rem_idx 이용해 (value, idx) 꼴로 저장
            # 이 때 value인 food_times[x] 는 cycle의 값을 빼준 만큼 저장되어 있어야 함
            for x in rem_idx:
                heapq.heappush(heap, (food_times[x]-cycle,x))

            # cycle 값 재할당
            cycle = remain // len(rem_idx)
            sub_remain = remain % len(rem_idx)
            # 최소힙에서 cycle보다 작거나 같은 원소를 모두 remove
            # cycle을 돈 뒤 접시가 비워지는 원소들을 제거해주는 것
            while heap[0][0] <= cycle:
                heapq.heappop(heap)

            # rem_idx 초기화
            rem_idx.clear()
            # 최소힙에 남아 있는 원소들 중 remain번째의 인덱스+1이 answer
            # 최소힙에 남아 있는 원소들의 idx 기준으로 오름차순으로 정렬
            rem_idx = [x[1] for x in heap]
            rem_idx.sort()

            # answer
            answer = rem_idx[sub_remain] + 1



        # answer
        return answer

print("6:", solution([5, 7, 1, 3, 4, 2], 6))
print("7:", solution([5, 7, 1, 3, 4, 2], 7))
print("8:", solution([5, 7, 1, 3, 4, 2], 8))
print("9:", solution([5, 7, 1, 3, 4, 2], 9))
print("10:", solution([5, 7, 1, 3, 4, 2], 10))
print("11:", solution([5, 7, 1, 3, 4, 2], 11))
print("12:", solution([5, 7, 1, 3, 4, 2], 12))
print("13:", solution([5, 7, 1, 3, 4, 2], 13))
print("14:", solution([5, 7, 1, 3, 4, 2], 14))
print("15:", solution([5, 7, 1, 3, 4, 2], 15))
print("16:", solution([5, 7, 1, 3, 4, 2], 16))
print("17:", solution([5, 7, 1, 3, 4, 2], 17))
print("18:", solution([5, 7, 1, 3, 4, 2], 18))

💭 アイデア

(1)
正直にぐるぐる回って食べ物を食べる時間を与え、食べ物を食べる時間が0以下ならスキップしてコードを書きます.
そのため、正確性テストに合格したかもしれませんが、効率テストには合格しませんでした.
(2)
そして、効率テストに合格するために、
k//食べ物の数で何回か循環した後
私はheapqでコードを書いて、食べ物を食べる時間が周期より小さい食べ物を取り除いてみました.
余数が0のときにずれが生じ,正しい答えは得られなかった.
🔽最後に解説を見て...🔽

🤓 問題の説明

01

この問題は、時間のかかる食べ物の貪欲さを確認する方法で解決することができる.すべての食べ物を時間基準に並べ替えて、時間の少ない食べ物から取り除くといいでしょう.このため、優先順位キューを使用して実装できますが、考慮すべき問題が多いため、難しい場合があります.

02

簡単な例として、Kを15秒と呼ぶ3つの食べ物がある.

1番食事:8秒

2番食事:6秒

3番食事:4秒

🔷 STEP 0
初期段階では、すべての食べ物を優先順位キュー(最小臀部)に挿入します.また、最後にK秒後に食べる食べ物の番号を出力するので、優先順位列に挿入する場合(食べ物時間、食べ物番号)はtupleとして挿入します.その形態は以下の通りである.

総残存時間(K):15秒

残菜:3個

🔷 STEP 1
第1段階では、最小限の食べ物が必要な3番の食べ物を取り除きます.ただし、まだ3つの食べ物が残っているので、3(残りの食べ物の個数)*4(3回の食べ物を食べる時間)=12を外します.言い換えれば、3番の食べ物を食べ終わるのに12秒かかります.その結果、残りの時間は15秒から3秒に減少します.

総残存時間(K):3秒

残菜:2個

で食べた食べ物:

🔷 STEP 2
残りの時間は3秒で、この段階で2番の食べ物を抜きます.食べ物が2つ残っているので、この段階で減らした時間は2(残りの食べ物の個数)*2(2番の食べ物を食べ終わる時間)=4秒です.
でも残り時間は3秒で、これは4より小さいので外さないでください.
そのため、「次に食べる」食べ物の番号を見つけて印刷すればいいのです.下図のように、毎秒食べる食べ物を一列に並べます.残り時間は3秒なので、4番麺の番号をプリントアウトすればいいです.

総残存時間(K):3秒

残菜:2個

だから2番の食べ物を出力します.

03

ソースコードは以下のように,筆者はheapqを用いて優先キューを実現する.優先度キューの内容については、マルチタスクアルゴリズムセクションで説明したが、ここではさらに説明しない.

🤓 回答例

import heapq

def solution(food_times, k):
    # 전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    # 시간이 작은 음식부터 빼야 하므로 우선순위 큐를 이용
    q = []
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 우선순위 큐에 삽입
        heapq.heappush(q, (food_times[i], i + 1))  

    sum_value = 0 # 먹기 위해 사용한 시간
    previous = 0 # 직전에 다 먹은 음식 시간
    length = len(food_times) # 남은 음식의 개수

    # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 k 비교
    while sum_value + ((q[0][0] - previous) * length) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1 # 다 먹은 음식 제외
        previous = now # 이전 음식 시간 재설정

    # 남은 음식 중에서 몇 번째 음식인지 확인하여 출력
    result = sorted(q, key=lambda x: x[1]) # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % length][1]

Osum valueの値を更新することが重要です
sum value+☆(現在の食事時間-以前の食事時間)*現在の食事個数☆とk比較
カウンセリングの状態は、以前のものを食べた後、現在のものも食べられるかどうかを判断することです.

🤔 コメント

KACOTECHとは簡単そうに見えますが、効率テストに合格するのは難しいです.

効率テストでは、優先順位キューを使用すべきだという考えさえ提案したが、私のアルゴリズムは正しい答えを与えなかった.

KACOTERにおいて,正確性と効率性を満たさなければならないことを認識した.

Pythonのlambdaとは何ですか?(解答例最後の行)

+)Ramda式(lambda express)
関数の作成と適用を容易にします.特定の機能を実行する関数を1行に作成できるのが特徴です.

def add(a, b):
	return a + b

# 일반적인 add() 메서드 사용
print(add(3, 7))

# 람다 표현식으로 구현한 add() 메서드
print((lambda a, b: a+ b)(3, 7))

Pythonのソートライブラリを使用する場合、ソート基準となるキーを設定する場合にもよく使用されます.