<덱deque> 백준 1021번 회전하는 큐

작성코드

#include <iostream>
#include <deque>

using namespace std;

int main()
{	
	//1.덱에 N개의 자연수를 채워넣는다.
	int N, M;
	cin >> N >> M;

	deque<int> deq;
	//2.M개의 원소를 넣을때까지 반복한다.
	for (int i = 0; i < N; i++)
	{
		deq.push_front(i);
	}

	int count = 0;

	for(int j = 0; j < M; j++)
	{
		int inputNum;
		cin >> inputNum;
		//3.덱을 앞부분부터 순회해서 뽑으려는 원소가 있으면 연산 1을 수행한다.
		for (int k = *deq.begin(); k != *deq.end(); k++)  //이터레이터는 주소값이다. +상수시간??
		{	//덱이 짝수개이면 8일때 4를 뽑으려면 1~4구간을 검사  (8 / 2 + 8 % 2)만큼 반복
		    //덱이 홀수개이면 9일때 3을 뽑으려면 1~5구간을 검사  (9 / 2 + 9 % 2)만큼 반복
			int checkPoint = deq.size() / 2 + deq.size() % 2;

			if (inputNum = deq[k])
			{//연산1: 첫번째 원소를 뽑고 삭제 
				deq.pop_front();
			}
			//4.뽑으려는 원소가 아닐때
			//4-1) 뽑으려는 원소가 인덱스상 중간위치에 있는 원소보다 작다면 연산2를 수행한다.
			else if ( ( inputNum != deq[k]) && (inputNum < deq.at(checkPoint)))
			{
			 //연산2: 왼쪽으로 한 칸 이동  첫번째 원소를 맨뒤로 보내기 
			 //덱에들어있는 원소가 뽑으려는 원소면 연산1수행
				deq.push_back(deq.front());
				deq.pop_front();
			 //뽑으려는 원소가 배열의 중간값보다 작으면 연산2수행하고 count	
				count++;
			}
			//4-2) 뽑으려는 원소가 인덱스상 중간위치에 있는 원소보다 크다면 연산3을 수행한다.
			else if ((inputNum != deq[k]) && (inputNum > deq.at(checkPoint)))
			{
			 //연산3: 오른쪽으로 한칸이동 마지막 원소를 첫번째로 보내기
				deq.push_front(deq.back());
				deq.pop_back();
			 //뽑으려는 원소가 배열의 중간값보다 크면 연산2수행하고 count	
				count++;
			}
		}	//5.연산2나 연산3을 수행했다면 연산1을 수행한다.
	}
	cout << count;
}

 

1. 덱에 N개의 자연수를 채워넣는다.
2. M개의 원소를 추출할 때까지 반복한다.
3. 덱을 앞부분부터 순회하여 뽑으려는 원소를 찾는다.
   • 뽑으려는 원소가 덱의 앞부분에 있다면 연산 1을 수행한다.
     • 연산 1: 첫 번째 원소를 뽑고 삭제한다.
   • 덱의 크기에 따라 중간 위치를 결정한다.
     • 짝수 크기 덱(size = 8)에서 4를 뽑으려면 1~4 구간 검사
       → (size / 2 + size % 2) 만큼 반복
     • 홀수 크기 덱(size = 9)에서 3을 뽑으려면 1~5 구간 검사
       → (size / 2 + size % 2) 만큼 반복
4. 뽑으려는 원소가 첫 번째가 아닐 경우, 위치에 따라 회전 연산을 수행한다.
   • 4-1) 뽑으려는 원소가 덱의 중간값보다 작다면 연산 2를 수행한다.
     • 연산 2: 왼쪽으로 한 칸 이동 (첫 번째 원소를 맨 뒤로 이동)
     • 연산 2 수행 후 다시 검사
     • count 증가 (이동 횟수 기록)
   • 4-2) 뽑으려는 원소가 덱의 중간값보다 크다면 연산 3을 수행한다.
     • 연산 3: 오른쪽으로 한 칸 이동 (마지막 원소를 첫 번째로 이동)
     • 연산 3 수행 후 다시 검사
     • count 증가 (이동 횟수 기록)
5. 연산 2나 연산 3을 수행했다면, 다시 연산 1을 수행하여 원소를 제거한다.

이 방법이면 최소한의 이동 횟수로 원하는 원소를 효율적으로 추출할 수 있다고 생각했다.

 

 

문제발생

 

 

 

문제 1. 비어있는덱에서 begin()을 호출한후 증가 시키는 경우 문제가 발생했다.

문제 2. pop을 하면 deq의 사이즈가 변화한다. int checkPoint 변수는 deq의 사이즈가 변할때마다 바뀐다.

잘못된 값으로 구간검사를 해서 pop 수행이 제대로 되지 않았다.

 

수정 코드

#include <iostream>
#include <deque>

using namespace std;

int main()
{	
	int N, M;
	cin >> N >> M;

	deque<int> deq;
	//2.N개의 원소를 넣을때까지 반복한다
	for (int i = 1; i <= N; ++i)
	{
		deq.push_back(i);
	}
	
	int count = 0;
	//M개의 원소를 뽑을때까지 반복
	//int checkPoint = deq.size() / 2 + deq.size() % 2;  //deq[checkpoint]가 push,pop할때마다 바뀜

	while(M--)
	{
		int inputNum;
		cin >> inputNum;
		
		//
		int idx = 0;
		for (int i = 0; i < deq.size(); i++)
		{
			if (inputNum == deq.at(i))
			{
				idx = i;
				break;
			}
		}
		//3.덱을 앞부분부터 순회해서 뽑으려는 원소가 있으면 연산 1을 수행한다.
			
		//4.뽑으려는 원소가 아닐때
		//4-1) 뽑으려는 원소가 인덱스상 중간위치에 있는 원소보다 작다면 연산2를 수행한다.
		if (idx < deq.size() / 2 + deq.size() % 2)
		{
		 //연산2: 왼쪽으로 한 칸 이동  첫번째 원소를 맨뒤로 보내기 
		 //덱에들어있는 원소가 뽑으려는 원소면 연산1수행 
			for (int i = 0; i < idx; i++)
			{
				deq.push_back(deq.front());
				deq.pop_front();
				//뽑으려는 원소가 배열의 중간값보다 작으면 연산2수행하고 count	
				count++;
			}
		}
		//4-2) 뽑으려는 원소가 인덱스상 중간위치에 있는 원소보다 크다면 연산3을 수행한다.
		else
		{
			for (int j = 0; j < deq.size() - idx; j++)
			{
				//연산3: 오른쪽으로 한칸이동 마지막 원소를 첫번째로 보내기
				deq.push_front(deq.back());
				deq.pop_back();
				//뽑으려는 원소가 배열의 중간값보다 크면 연산2수행하고 count	
				count++;
			}
		}
	//5.연산2나 연산3을 수행했다면 연산1을 수행한다.
		deq.pop_front();
	}
	std::cout << count;
}

 

변수 idx의 값을 입력받은 원소와 같아질때까지 증가시킨다. 그리고 입력받은 원소 대신 idx를 이용해서 비교연산을 한다. 그렇게 되면 처음 덱에있는 인덱스가 그대로 유지되므로 덱사이즈의 영향을 받지 않을수있다.