[백준 알고리즘 c++] 문제 67. 회전하는 큐 1021

알고리즘

 

[문제]

 

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

[나의 풀이]

 

1. 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
1. 큐의크기 N과 뽑아내려는 개수 M을 입력 받는다.
2. M개 만큼 뽑아내려는 수의 위치를 입력 받는다.
처리
1. 1번 절차를 제외한 2,3번 절차를 이용해 해당 원소의 지점까지 가는 방법을 카운트 한다.
2. 해당 지점에 갔으면 원소를 삭제하고 다음 원소를 찾으러 간다.

[소스 코드]

 

#include <iostream>
#include <deque>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	//
	// 문제
	// 1. 연산의 최솟값을 출력하는 프로그램을 작성하시오.
	// 입력
	// 1. 큐의크기 N과 뽑아내려는 개수 M을 입력 받는다.
	// 2. M개 만큼 뽑아내려는 수의 위치를 입력 받는다.
	// 처리
	// 1. 1번 절차를 제외한 2,3번 절차를 이용해 해당 원소의 지점까지 가는 방법을 카운트 한다.
	// 2. 해당 지점에 갔으면 원소를 삭제하고 다음 원소를 찾으러 간다.
	// 출력
	//

	int N , M;
	
	cin >> N >> M;
	deque<int> dq;
	deque<int> dq2;
	for (int i = 1; i <= N; i++)
	{
		dq.push_back(i);
		dq2.push_back(i);
	}

	int count = 0;
	for (int i = 0; i < M; i++)
	{
		int num = 0;
		cin >> num;

		int leftCount = 0;
		int rightCount = 0;
		//num값이 어디 위치해 있는지 찾고 count 해주기
		//앞으로 가고 뒤로 가서 어떤 값이 최솟값인지 구하고 최솟값으로 출력하기
		while (!dq.empty())
		{
			if (dq.front() == num)
			{
				break;
			}
			dq.push_back(dq.front());
			dq.pop_front();
			leftCount++;
		}

		while (!dq2.empty())
		{
			if (dq2.front() == num)
			{
				break;
			}
			dq2.push_front(dq2.back());
			dq2.pop_back();
			rightCount++;
		}

		if (leftCount < rightCount)
		{
			count += leftCount;
		}
		else
		{
			count += rightCount;
		}

		dq.pop_front();
		dq2.pop_front();
	}
	
	cout << count;

	return 0;
}

다른 풀이)

#include <iostream>
#include <deque>

using namespace std;

int main(int argc, char**argv) {

	ios::sync_with_stdio(0);
	cin.tie(0);
		
	deque<int> DQ;
	int N, M;
	int left, right;
	int cnt = 0;
	
	cin >> N >> M;
	
	for(int i=1; i<=N; i++){
		DQ.push_back(i);
	}
	

	while(M--){
		int num;
		cin >> num;
		
		for(int i=0; i<DQ.size(); i++){
			
			if(DQ[i] == num){
				left = i;
				right = DQ.size()-i;
				break;
				
			}
		}
		
		if(left<=right){
			while(1){
				if(DQ.front()==num)
					break;

				DQ.push_back(DQ.front());
				DQ.pop_front();
				cnt++;
				
			}
			DQ.pop_front();
		}
		
		else{
			cnt++;
			while(1){
				if(DQ.back()==num)
					break;
	
				DQ.push_front(DQ.back());
				DQ.pop_back();
				cnt++;
				
			}
			DQ.pop_back();
		}

	}
	
	cout << cnt;
	
	return 0;
}

[피드백]