[白俊]164号:カード2
質問する
心得
常にタイムアウトが発生し,Pythonライブラリに集合したdeque実装コードを用いて解決できる.
dequeの速度はlistよりも速いので、pop(0)などのメソッドを実行する場合は、リストに対してO(N)演算を実行するが、dequeはpopleft()などのメソッドを用いてO(1)演算を実行する.
dequeには以下の追加方法があります.
タイムアウト問題を解決するために、Deque資料型を使用せざるを得ない.
Deque(Deck)
双方向キューなどの要素を前後2方向に追加または削除できるデータ構造.
つまり、前後2方向から要素を追加または削除できるので、両端要素のappendとpopは圧倒的に速い!
コンテナの両端の要素にアクセスして挿入または削除する場合、通常のリスト(list)はこれらの演算にO(n)を必要とするのとは逆に、DequeはO(1)にアクセスすることができる.
deq.rotate(n)
deque(a)でdequeオブジェクトを作成した後、rotate関数を使用して2の右側に回転します.
2を左に回転させる場合は、2ではなく2を入力します.
スタック
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
正解を解く
心得
常にタイムアウトが発生し,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])
Reference
この問題について([白俊]164号:カード2), 我々は、より多くの情報をここで見つけました https://velog.io/@letsbebrave/백준-2164번-카드2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol