[1021] 회전하는 큐

처음에 C++쓰는 김에 배열을 사용해서 circleQueue 클레스로 만들어보자 했는데 계속 틀렸습니다가 떴다.

반례를 못찾아서 다시 덱으로 구현했다.

1. 덱의 맨 앞부분의 숫자가 현재 찾고자 하는 숫자와 같으면 덱에서 pop()
2. 아니라면 현재 찾고자 하는 숫자의 인덱스가 앞쪽에 가까운지, 뒤쪽에 가까운지 검사
3. 앞쪽에 가까우면 덱의 맨 앞 원소를 덱의 맨 뒤로,
4. 뒤쪽에 가까우면 덱의 맨 뒤 원소를 덱의 맨 앞으로 옮긴다.

위 과정을 입력받으로 받은 큐가 빌 때까지 반복한다.

---

#include <cstdio>

#include <deque>

#include <queue>

using namespace std;

deque<int> dq;

int getIndex(int n)

{

int ret = 0;

for (int i = 0; i < dq.size(); i++)

{

if (dq[i] == n)

{

ret = i;

break;

}

}

return ret;

}

int main()

{

int N, M = 0;

queue<int> Q;

scanf("%d %d", &N, &M);

for(int i = 0;i<N;i++){

dq.push_back(i+1);

}

int temp = 0;

for (int i = 0; i < M; i++)

{

scanf("%d", &temp);

Q.push(temp);

}

int res= 0;

while (!Q.empty())

{

if (dq.front() == Q.front())

{

dq.pop_front();

Q.pop();

}

else if (getIndex(Q.front()) > dq.size() / 2)

{

dq.push_front(dq.back());

dq.pop_back();

res++;

}

else

{

dq.push_back(dq.front());

dq.pop_front();

res++;

}

}

printf("%d\n", res);

}