[boj](s 4)1021回転キュー
✅ deque
質問する
の左端(最初の要素)を抽出します. の一番左(一番目の要素)を一番右(一番後ろ)に置きます. の一番右側(最後の要素)を一番左(一番目)に入れます. 所定の要素を所定の順序で抽出するために必要な2、3回の演算の最大値出力の問題.
つまり、必要な要素を選択すると、1番の演算は一番左にしかできません.
キューを移動する方法は2,3回の演算で完了する.
これは双方向ループキューで、両方ともpopとpushを使用するためdexを使用する必要があります.
2、3回の演算の最大値は、キューの移動を最小化し、引き抜くことです.
したがって、選択する要素は、少なくともキューの左側または右側に移動し、最初の位置にある必要があります.(1番演算で抽出する必要があるため)
注意が必要なのは、右に移動すると本人も前に移動するので、移動回数は+1になります.
すなわち,自分の標準「左要素の数」を「右要素の数+1」と比較してより小さい方向に移動する.
O(N)
問題では双方向キューについて言及しているので,インデックスを用いる判断自体は難しくないが,問題は要素の除去方向が左のみであり,左と右に移動すると最適な方向を探す過程でトラップがあることである.
質問する
リンク
に答える
1.質問へのアクセス
問題の演算タイプに応じて、
1.質問へのアクセス
問題の演算タイプに応じて、
つまり、必要な要素を選択すると、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.問題の重要な部分
問題では双方向キューについて言及しているので,インデックスを用いる判断自体は難しくないが,問題は要素の除去方向が左のみであり,左と右に移動すると最適な方向を探す過程でトラップがあることである.
Reference
この問題について([boj](s 4)1021回転キュー), 我々は、より多くの情報をここで見つけました https://velog.io/@peanut_/boj-1021-회전하는-큐テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol