[BOJ알고리즘, C++]#1021_회전하는 큐
BOJ 알고리즘 문제 풀이, 1021번 문제 회전하는 큐
deque 컨테이너를 활용하는 방법에 대해 알아보겠습니다.
Overview
- 문제
- 풀이
- 코드
#0. 문제
#1. 풀이
1. 덱
- 덱(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
- operator [] : 덱의 임의의 위치에 접근
- front() : 덱의 가장 앞에 위치한 요소에 접근
- back() : 덱의 가장 마지막에 위치한 요소에 접근
- push_front() : 덱의 가장 앞쪽에 새로운 항목 삽입
- puh_back() : 덱의 가장 마지막에 새로운 항목 삽입
- pop_front() : 덱의 가장 앞쪽에 위치한 항목 제거
- 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;
}
'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글
[BOJ알고리즘, C++]#1966_프린터 큐, 우선순위 큐, 큐 (0) | 2023.06.22 |
---|---|
[BOJ알고리즘, C++]#18258_큐2, 선형 자료구조, 큐 (0) | 2023.06.22 |
[BOJ알고리즘, C++]#11866_요세푸스 문제0, 선형 자료구조, 큐 (0) | 2023.06.06 |
[BOJ알고리즘, C++]#2164_카드2, 선형 자료구조, 큐 (0) | 2023.06.06 |
[BOJ알고리즘, C++]#7785_회사에 있는 사람, 연결 자료구조, Set 컨테이너 활용 (0) | 2023.06.06 |