[アルゴリズム]プログラマ-表の編集

プログラマ-表の編集

他人を解く

def solution(n, k, cmd):
    exists = [True for _ in range(n)]
    up = [-1] + [x for x in range(n-1)]
    down = [x for x in range(1, n)] + [-1]
    deleted = []

    for c in cmd:
        op = c[0]

        if op == "U":
            val = int(c.split()[1])
            for _ in range(val):
                k = up[k]

        elif op == "D":
            val = int(c.split()[1])
            for _ in range(val):
                k = down[k]

        elif op == "C":
            if up[k] != -1:
                down[up[k]] = down[k]
            if down[k] != -1:
                up[down[k]] = up[k]
            exists[k] = False
            deleted.append(k)
            k = down[k] if down[k] != -1 else up[k]

        elif op == "Z":
            d = deleted.pop()
            if up[d] != -1:
                down[up[d]] = d
            if down[d] != -1:
                up[down[d]] = d
            exists[d] = True

    return ''.join(["O" if x else "X" for x in exists])

print(solution(8, 2, ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"]) == "OOOOXOOO")
print(solution(8, 2, ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"]) == "OOXOXOOO")

ソース:https://velog.io/@kerri/Swift-Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Lv3-%ED%91%9C-%ED%8E%B8%EC%A7%91-2021-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%B1%84%EC%9A%A9%EC%97%B0%EA%B3%84%ED%98%95-%EC%9D%B8%ED%84%B4%EC%8B%AD
実際の問題に従って実現すれば、タイムアウトします.
位置がnowの場合、上に移動する場合は、どのインデックスを指すべきか、下に移動する場合はどのインデックスを指すべきかを保存します.

index	up	down 				up	down
0	-1	1				-1	1
1	0	2				0	2
2	1	3				1	4
3	2	4	-> index 3을 삭제 -> 	2	4
4	3	5				2	5
5	4	6				4	6
6	5	7				5	7

U演算
U演算では、上に検索するcnt数が最も多い.now位置でup[now]を繰り返しブラウズすればよい.
(now -> up[now] -> up[up[now]] ...)

D演算
CNTの数を下に検索します.down位置でdown[now]を繰り返し検索すればよい.
(down -> down[now] -> down[down[now]] ...)

C演算
削除操作なのでexist[now]をfalseに設定します.削除したインデックスを保存するdelete stackにnowを追加します.
nowが一番上の行でない場合は、down[up[now]=down[now]に置き換えます.
nowが一番下の行でない場合はup[down[now]=up[now]に置き換えます.
削除した行が最後の行の場合はnow=up[now]を使用します.
最後の行でない場合はnow=down[now]に変更します.

Z演算
delete stackから最後のインデックスの値を取得します.
exist[idx]=true.
idxが一番上の行でない場合は、down[up[idx]=down[idx]で置き換えます.
idxの一番下の行でない場合は、up[down[idx]=up[idx]で置き換えます.