[BOJ알고리즘, C++]#1021_회전하는 큐, 선형 자료구조, 덱

 

[BOJ알고리즘, C++]#1021_회전하는 큐

 

BOJ 알고리즘 문제 풀이, 1021번 문제 회전하는 큐

deque 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

 

 

#1. 풀이

1. 덱

[자료 구조]#0_선형 자료구조

 

[Basic C++] #68_deque

 

• 덱(Double Ended Queue)은 선형 자료구조 중 큐와 스택의 특성을 모두 가지고 있는 선형 자료구조입니다. 덱은 원소의 삽입과 삭제를 양쪽 끝에서 수행하는 큐의 확장된 버전입니다.
• 덱은 양쪽 끝에서 삽입/제거가 가능합니다. 큐의 FIFO 동작 방식과 스택의 LIFO 동작 방식을 모두 수행할 수 있습니다.

 

2. deque 컨테이너

#include <iostream>
#include <deque>

using namespace std;

int main() {

	deque<int> dq = { 1, 2, 3, 4, 5 };

	// #1. operator[]	: 임의의 접근
	int a = dq[0];

	// #2. front()		: 덱의 가장 앞에 위치한 요소 접근
	int b = dq.front();

	// #3. back()		: 덱의 가장 마지막에 위치한 요소 접근
	int c = dq.back();

	// #4. push_front()	: 새 항목 덱의 앞쪽에 삽입
	dq.push_front(0);

	// #5. push_back()	: 새 항목 덱의 뒤쪽에 삽입
	dq.push_back(6);

	// #6. pop_front()	: 덱의 가장 앞쪽에 위치한 항목 제거
	dq.pop_front();

	// #7. pop_back()	: 덱의 가장 마지막에 위치한 항목 제거
	dq.pop_back();

	return 0;
}

 

Details

 

1. operator [] : 덱의 임의의 위치에 접근
2. front() : 덱의 가장 앞에 위치한 요소에 접근
3. back() : 덱의 가장 마지막에 위치한 요소에 접근
4. push_front() : 덱의 가장 앞쪽에 새로운 항목 삽입
5. puh_back() : 덱의 가장 마지막에 새로운 항목 삽입
6. pop_front() : 덱의 가장 앞쪽에 위치한 항목 제거
7. pop_back() : 덱의 가장 마지막에 위치한 항목 제거

 

3. 덱의 임의의 접근과 삽입/제거

#include <iostream>
#include <deque>

using namespace std;

int main() {
	deque<int> dq = { 1, 2, 3, 4, 5 };

	int num = 5;
	int Idx = 0;

	for (int i = 0; i < dq.size(); i++)
	{
		if (dq[i] == num)
			Idx = i;
	}

	cout << dq[Idx] << endl;

	return 0;
}

 

Details

 

• deque 컨테이너는 STL 컨테이너 중 queue 혹은 stack 컨테이너들과 달리 operator []를 통해 임의의 접근이 가능하여 for문을 통해 컨테이너를 순회할 수 있습니다.
• 우리가 찾고자 하는 숫자의 인덱스를 찾고, 해당 인덱스의 위치가 덱의 왼쪽 끝과 가까운지 혹은 오른쪽 끝과 가까운지 판단합니다.
• 왼쪽과 가깝다면, 덱을 왼쪽으로 회전 시키고 그렇지 않다면 오른쪽으로 회전시킵니다.
• 최종적으로 덱을 회전한 횟수를 출력합니다.

 

#2. 코드

1. 코드

#include <iostream>
#include <queue>
using namespace std;

int N, M;
int num;

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    deque<int> dq;
    int ans = 0;
    
    cin >> N >> M;
    
    for(int i=1; i<=N; i++)
    {
        dq.push_back(i);
    }
    
    while(M--)
    {
        cin >> num;
        int Idx = -1;
        for(int i=0; i<dq.size(); i++)
        {
            if(dq[i] == num)
            {    
                Idx = i;
                break;
            }
        }
        // 1. 왼쪽 회전
        if(Idx < dq.size()-Idx)
        {
            while(1)
            {
                if(dq.front() == num)
                {
                    dq.pop_front();
                    break;
                }
                ans++;
                dq.push_back(dq.front());
                dq.pop_front();
            }
        }
        // 2. 오른쪽 회전
        else
        {
            while(1)
            {
                if(dq.front() == num)
                {
                    dq.pop_front();
                    break;
                }
                ans++;
                dq.push_front(dq.back());
                dq.pop_back();
            }
        }
    }
    cout << ans;
}