[C++] 백준 1021 : 회전하는 큐
#include <iostream>
#include <deque>
using namespace std;
int N, M, cnt = 0, x;
deque<int> dq;
int main(int argc, char** argv){
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; i++){
dq.push_back(i); // 큐 초기화
}
int A[M];
for(int i = 0; i < M; i++){
scanf("%d", &A[i]);
}
for(int i = 0; i < M; i++){
int left = 0, right = 0;
while(1){
if(dq.front() == A[i]){
break;
}
dq.push_back(dq.front()); // 앞의 값 뒤로 넘기기
dq.pop_front();
left++;
}
for(int j = 0; j < left; j++){
dq.push_front(dq.back());
dq.pop_back(); // 원래대로 돌리기
}
right = dq.size() - left; // right 값은 자동으로 구할 수 있다.
if(left < right){
cnt += left;
while(left--){
dq.push_back(dq.front()); // 앞의 값 뒤로 넘기기
dq.pop_front();
}
dq.pop_front();
} else {
cnt += right;
while(right--){
dq.push_front(dq.back()); // 뒤의 값 앞으로 넘기기
dq.pop_back();
}
dq.pop_front();
}
}
printf("%d", cnt);
return 0;
}
생각보다 단순무식하게 푸는게 옳을때도 있다. 왼쪽으로 빼는 것이 빠를지 오른쪽을 빼는 것이 빠를지 확인하기 위해서는 직접 빼보면서 구하면 된다.
하나를 구하면 하나는 바로 구할 수 있으므로 그냥 큐의 크기에서 왼쪽으로 뺐을 때를 오른쪽에서 뺐을 때로 구하면 된다.
Author And Source
이 문제에 관하여([C++] 백준 1021 : 회전하는 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1021-회전하는-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)