✅ deque

質問する

リンク

に答える

1.質問へのアクセス

問題の演算タイプに応じて、

の左端(最初の要素)を抽出します.

の一番左(一番目の要素)を一番右(一番後ろ)に置きます.

の一番右側(最後の要素)を一番左(一番目)に入れます.

所定の要素を所定の順序で抽出するために必要な2、3回の演算の最大値出力の問題.
つまり、必要な要素を選択すると、1番の演算は一番左にしかできません.
キューを移動する方法は2,3回の演算で完了する.

2.資料構造の選択とその原因

これは双方向ループキューで、両方ともpopとpushを使用するためdexを使用する必要があります.

3.トラブルシューティングロジック（解法）

2、3回の演算の最大値は、キューの移動を最小化し、引き抜くことです.
したがって、選択する要素は、少なくともキューの左側または右側に移動し、最初の位置にある必要があります.(1番演算で抽出する必要があるため)
注意が必要なのは、右に移動すると本人も前に移動するので、移動回数は+1になります.
すなわち,自分の標準「左要素の数」を「右要素の数+1」と比較してより小さい方向に移動する.

ぎじふごう

cin >> num

// 왼쪽, 오른쪽 원소의 수 세기
for(i = 0 ~ dq.size){
	if(dq[i] == num){
    	left = i
        right = dq.size - left - 1
    }
}

// 왼쪽 이동
if(left <= right + 1){
	while(1){
    	if(dq.front == num) break;
        tmp = dq.front
        dq.push_back(tmp)
        dq.pop_front
        cnt++
    }
    dq.pop_front
}
else{ // 오른쪽 이동
    while(1){
    	if(dq.front == num) break;
        tmp = dq.back
        dq.push_front(tmp)
        dq.pop_back
        cnt++
    }
    dq.pop_front
}

cout << cnt

4.時間複雑度分析

O(N)

5.問題の重要な部分

問題では双方向キューについて言及しているので,インデックスを用いる判断自体は難しくないが,問題は要素の除去方向が左のみであり,左と右に移動すると最適な方向を探す過程でトラップがあることである.