[白俊#2493]塔

4830 ワード
白駿 ps boj アルゴリズム#アルゴリズム# スタック テキストリンク

1.問題の説明



2.解説


O(n^2)の時間的複雑さで解き始めたところ,タイムアウトが発生し,時間的複雑さをどのように減らすかを考えた.
  • まず左からタワーをチェックし、インデックス、値のペアを組み合わせてスタックに挿入します.
  • idxは、1からスタックがアイドルになるまでスタックの一番上のvalがスタックの一番上のvalよりも大きい場合、結果配列にスタックの一番上の値を挿入します.そうしないとスタックはポップアップします()
  • while文が終了すると、現在のインデックスと値のペアがスタックに挿入されます.
    • 説明がもっと難しいので、コードを読んでほしいです.私は本当に説明できません.

    3.コード

    import sys
input = sys.stdin.readline

N = int(input())
tower = list(map(int, input().split()))
stack = []
res = [0] * N

for idx, val in enumerate(tower):
    if idx == 0:
        stack.append([idx, val])
        continue
    else:
        while stack:
            if val < stack[-1][1]:
                res[idx] = stack[-1][0] + 1
                break
            else:
                stack.pop()
        stack.append([idx, val])

print(" ".join(map(str, res)))
    B2. Palindrome Game (hard version) #721 Div.2
    2178号:迷宮ナビゲーション