コンテキスト依存データ構造

エンコードテストはタイミングテストなので、問題のタイプを理解し、そのタイプに合ったデータ構造を素早く考えることが重要です.そのため、お客様の状況に合ったデータ構造を整理します.
👨 Hash
Pythonではdictionaryでハッシュを実現できます.
dictionaryは、挿入、削除、クエリー時間の複雑さがO(1)であるという利点があるため、問題を迅速に解決することができる.
(O(1)なので、時間の複雑さは影響を受けないと考える必要はありません.)
また、KeyとValueでストレージの特徴を知る必要があります.
したがって、検索、挿入、削除操作を迅速に処理し、リストとして処理する必要がある場合は、時間的な複雑さの問題が発生する可能性があります.
検索、挿入、削除が高速であるため、適用例は、特定の重複要素の出力頻度などに使用できます.
また、ソートが必要な場合は、ソートがないため、ソートを考慮する必要があります.

d1 = dict() # 빈 딕셔너리 선언
d2 = {} # 빈 딕셔너리 선언

d[k] = value # (k,v) 쌍을 추가
d.pop(k) # key가 k인 것을 찾아서 제거
k in d # 딕셔너리 d 안에 key가 k인 쌍이 있는지 여부를 확인해서 있다면 True 없다면 False를 반환

pop()などを使用する場合、対応するキーがない場合は、エラーを回避するために常にk in dを使用することをお勧めします.
整列されたバイナリファイルを使用する場合は、外部ライブラリを使用してコンテナをソートすることもできます.
(ただし,符号化テストではソート後のバイナリのみで解くという問題は生じず,実際の使用率が高い.
挿入、削除、およびクエリは、O(logn)の時間的複雑さを有する.
使用方法はdict()と非常に似ています.「」を参照してください.

from sortedcontainers import SortedDict
sd = SortedDict() # 정렬된 딕셔너리 생성

👧 HashSet
Pythonにはsetというクラスがあります.
setとdictの最大の違いは、ペアで格納されていないことです.
ただし,Hashベースであるため,挿入と削除はいずれもO(1)である.
コレクションはコレクションであり、重複は許されません.
HashSetはペアストレージを必要とせず,要素の有無を比較する際に非常に有用である.
ある要素を比較する必要がある場合、リストはすべて検索する必要があるため、時間の複雑さはリストのサイズに依存し、setを使用してO(1)のように迅速に処理することができる.
この機能は、繰り返しは許可されず、順序を守る必要はありませんが、迅速な挿入、削除、クエリーが必要な場合に便利です.

s1 = set() # 빈 set 생성
s.add(E) # set에 데이터 E 삽입
s.remove(E) # set에 데이터 E 삭제
E in s # set에 데이터 E 유무를 확인하고 있다면 True 없다면 False를 반환

整列したセットを使用する場合は、外部ライブラリを使用してコンテナをソートすることもできます.
(ただし、符号化テストではソートセットのみが使用されるという問題はなく、実際の使用率が高い.)
挿入、削除、およびクエリは、O(logn)の時間的複雑さを有する.
使用法はset()と非常に似ています.を参照してください.

from sortedcontainers import SortedSet
s = SortedSet() # 정렬된 Set 생성

👵 優先キュー
FIFOフォーマットはキューと異なり、優先度キューは常に高優先度データのみに注目するデータ構造であることはよく知られている.
このデータ構造は、挿入、削除、およびクエリーをO(logN)として解析します.
PythonはPriorityQueueというクラスをサポートしていますが、速度が非常に遅いため、限られた時間で問題を解決することはほとんど不可能です.
したがってheapqを利用して優先順位キューを使用することができます.
なお、heapqはデフォルトでmax-heapではなくmin-heapを実現しているため、優先順位キューを実現するために要素に-(負の値)を付け、出力時に-を付けて、いくつかの小さなテクニック(?)を使用することができます.使役して解決することができる.
参考までに、それを使用する前に、Pythonが空のリストを作成する必要があることを忘れないでください~!

import heapq

# 아래의 예시는 min-heap이므로 우선순위 큐로 이용하시려면 음수를 붙여주세요!!
queue = [] # 빈 리스트 생성
heapq.heappush(queue, e) # 데이터 e를 삽입
heapq.heappop(queue) # 현재 데이터 최소 값을 제거
heapq[0] # 현재 최소값을 단순 출력 (삭제 X)