[白俊]164号:カード2


質問する

心得
常にタイムアウトが発生し,Pythonライブラリに集合したdeque実装コードを用いて解決できる.
dequeの速度はlistよりも速いので、pop(0)などのメソッドを実行する場合は、リストに対してO(N)演算を実行するが、dequeはpopleft()などのメソッドを用いてO(1)演算を実行する.
dequeには以下の追加方法があります.
appendleft(n) : 맨 앞에 데이터 n 입력하기
popleft() : 맨 앞에 있는 데이터 내보내기
コンセプト
タイムアウト問題を解決するために、Deque資料型を使用せざるを得ない.
Deque(Deck)
双方向キューなどの要素を前後2方向に追加または削除できるデータ構造.
つまり、前後2方向から要素を追加または削除できるので、両端要素のappendとpopは圧倒的に速い!
コンテナの両端の要素にアクセスして挿入または削除する場合、通常のリスト(list)はこれらの演算にO(n)を必要とするのとは逆に、DequeはO(1)にアクセスすることができる.
from collections import deque

deq = deque([1,2,3,4,5])

# 맨 앞에 데이터 입력
deq.appendleft(0) # deque([0, 1, 2, 3, 4, 5])

# 맨 뒤에 데이터 입력
deq.append(6) # deque([0, 1, 2, 3, 4, 5, 6])

# 맨 앞에 있는 데이터 출력
deq.popleft() # deque([1,2,3,4,5,6])

# 맨 뒤에 있는 데이터 출력
deq.pop() # deque([1,2,3,4,5])

# item을 데크에서 찾아 삭제한다.
deque.remove(item)
リストでnを回転する問題
deq.rotate(n)
deque(a)でdequeオブジェクトを作成した後、rotate関数を使用して2の右側に回転します.
2を左に回転させる場合は、2ではなく2を入力します.
from collections import deque
a = [1, 2, 3, 4, 5]
q = deque(a)
q.rotate(2)
result = list(q)
result
[4, 5, 1, 2, 3]
cf.
スタック
LIFO (last in first out)
後で入れるデータを先に返すように設計されたメモリ構造.
データ入力はpush>append()
出力はpop>pop()
リストを使用してスタック構造でデータを処理できます
キュー
FIFO(first in first out)
行、すなわち行データを先に返す
同様にリストを用いて実施する.
入力push>append()
出力get>pop(0)
最初に現れた0番目の要素を抜いて!!
注意:https://leonkong.cc/posts/python-deque.html
https://wikidocs.net/104977
正解を解く
import sys
from collections import deque

N = int(sys.stdin.readline())

numlist = []

for i in range(N):
    numlist.append(i+1)
    
deq = deque(numlist)

if N == 1:
    print(numlist[0])
elif N == 2:
    print(numlist[1])
else:
    for i in range(N-2):
        deq.popleft()
        num = deq.popleft()
        deq.append(num)
    print(deq[1])
タイムアウト解
import sys
N = int(sys.stdin.readline())

numlist = []

for i in range(N):
    numlist.append(i+1)

if N == 1:
    print(numlist[0])
elif N == 2:
    print(numlist[1])
else:
    for i in range(N-2):
        numlist.pop(0)
        num = numlist.pop(0)
        numlist.append(num)
    print(numlist[1])