-
1021) 회전하는 큐 c++백준코딩일기 2020. 11. 4. 20:57
문제 ) www.acmicpc.net/problem/1021
풀이 )
맨 처음 큐의 크기 N을 입력받으면 1~N 까지의 수를 가진 큐를 갖게 되고, M 번 뽑는다.
지민이가 뽑는 카드를 target 이라는 변수로 입력을 받고,
target 이 맨앞에 있다면 바로 pop_front 를해서 없앴고,
맨 앞에 있지 않다면 왼쪽으로 회전할지, 오른쪽으로 회전할지 정해야한다.
회전을 정하는 방법은 덱을 처음부터 돌면서 target 이 현재 덱에서 몇 번 째에 있는지 idx 를 이용해서 셌다.
큐의 전체 크기를 2로 나누고 +1 을 해서 그 값과 idx 값을 비교해서
(dq.size()/2) +1 의 값이 idx 보다 크다면 왼쪽으로 한 칸씩 이동하고
반대의 경우라면 오른쪽으로 한 칸씩 이동하도록 했다.코드 )
#include <iostream> #include <deque> using namespace std; int N, M, cnt, target, tmp; string cmd; deque<int> dq; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for(int i=1; i<=N; i++) dq.push_back(i); while(M--) { cin >> target; if(target == dq.front()) dq.pop_front(); else { int idx = 0; for( int e: dq){ if( e == target){ idx++; break; } idx++; } if(idx > (dq.size()/2)+1) { while(dq.front() != target) { tmp = dq.back(); dq.push_front(tmp); dq.pop_back(); cnt++; } } else{ while(dq.front() != target) { tmp = dq.front(); dq.push_back(tmp); dq.pop_front(); cnt++; } } dq.pop_front(); } } cout << cnt << "\n"; }
'백준코딩일기' 카테고리의 다른 글
1406) 에디터 c++ (0) 2020.11.05 5430) AC c++ (0) 2020.11.05 10866) 덱 c++ (0) 2020.11.04 2164) 카드2 c++ (0) 2020.11.04 18258) 큐2 c++ (0) 2020.11.04