BOJ 2493タワー

5233 ワード
2021.02.11 テキストリンク
https://www.acmicpc.net/problem/2493
時間1.5秒、メモリ128 MB
input :
  • N (1 <= N <= 500,000)
  • Nタワー高さ
    • output :
  • レーザ信号を受信したタワー番号を1つのスペースで出力します.レーザ信号を受信タワーがなければ、出力0は
    • である.
    塔の個数は50万です.これらのタワーを全部後ろから数えて探せば、最悪の場合50万*50万の数が...
    どうやって短縮しますか??
    前から比較する方法はありますか?
    いつものように、ブロガーを見つけてスタックを利用しました.
    スタックに格納(idx,height)し、1つずつ取り出して比較し、自分より大きい建物や同じ建物が見つかったら、このidx+1を正解に追加します.
    次に見つけた2つの建物をスタックに再入れ,比較対象とした.
    import sys

n = int(sys.stdin.readline())
heights = list(map(int, sys.stdin.readline().split()))
temp = [(0, 0)]
ans = []

for idx, item in enumerate(heights):
    flag = 0

	# 모든 temp에 들어있는 건물들을 비교하다가.
    while len(temp) > 0:
        compare_idx, compare_height = temp.pop()
        # 크거나 같은 것을 찾은 경우에 break로 빠져나감.
        if compare_height >= item:
            flag = 1
            break

    if flag:
    # compare 변수에 이 값들이 남아 있으니까 다시 temp 변수에 넣어주고,
    # 답을 업데이트 해준다.
        temp.append((compare_idx, compare_height))
        ans.append(compare_idx + 1)
    else:
        ans.append(0)
	
    # 현재까지의 값도 temp에 넣어주어서 비교대상이 되도록 한다.
    temp.append((idx, item))

for item in ans:
    print(item, end=" ")
    最初に印刷したものを早く見たいだけです.
    print(item)が間違っています
    [React] useEffect hook
    [ハッシュ]ベストアルバム