[2493]タワー

990 ワード
白駿 パイ スタック テキストリンク

質問する


KOI通信研究所はレーザーを利用した新しい秘密通信システムの開発実験を進めている.実験を行うために,1本の直線上にN個の異なる高さの塔を水平直線の左から右に順に立て,各塔の頂部にレーザエミッタを取り付けた.各タワーのレーザエミッタは、地表に平行な水平直線の左側にレーザ信号を送信し、タワーの柱にはレーザ信号を受信する装置が取り付けられている.1つのタワーから送信されるレーザ信号は、最初に出会った1つのタワーでしか受信できません.
ex)6,9,5,7,4,6,9があれば受信可能なタワーはないので,0,5,7は9人タワー,4は7人タワーで受信するので[0,0,2,4]となる.

コード#コード#

tc = int(input())
tower = list(map(int, input().split()))
razor = [0] * tc
stack = list()
stack.append(0)

for i in range(1, tc):
    while stack and tower[stack[-1]] < tower[i]:
        stack.pop()
    if stack:
        razor[i] = stack[-1] + 1
    stack.append(i)

for i in razor:
    print(str(i) + " ", end='')

説明:


完全に試行的な解答で、結果は当然タイムアウトしました.スタックを利用して解放することを知っていて、スタックの中で重複文だけを保存して、現在のタワーより高いタワー、タワーでなければpopはそれまでなくて、そして自分の位置をスタックの中で保存します.スタックが空いている場合は、今は自分より高いタワーがないことを意味しますので、受信できるタワーはありません.
[TIL]reactのupdate()
BOJ9461