<문제 소개>
<소스 코드>
#include <iostream>
#include <vector>
using namespace std;
struct Deque
{
private:
int* elements;
int frontIndex;
int backIndex;
int MAX_SIZE;
public:
Deque(int n)
{
elements = new int[n];
frontIndex = 0;
backIndex = 0;
MAX_SIZE = n;
}
void push_front(int x)
{
// front는 0부터 뒤로가면서 원소를 삽입
elements[frontIndex] = x;
frontIndex = ((frontIndex - 1) + MAX_SIZE) % MAX_SIZE;
}
void push_back(int x)
{
// back은 1부터 앞으로가면서 원소를 삽입
backIndex = (backIndex + 1) % MAX_SIZE;
elements[backIndex] = x;
}
int pop_front()
{
if (empty()) return -1;
else
{
// frontIndex는 항상 공백을 가리키므로 앞의 원소를 출력
frontIndex = (frontIndex + 1) % MAX_SIZE;
return elements[frontIndex];
}
}
int pop_back()
{
if (empty()) return -1;
else
{
// backIndex는 해당 자리의 원소가 마지막 원소를 가리키므로 해당 원소를 출력
int curBackIndex = backIndex;
backIndex = ((backIndex - 1) + MAX_SIZE) % MAX_SIZE;
return elements[curBackIndex];
}
}
int size()
{
return (backIndex - frontIndex + MAX_SIZE) % MAX_SIZE;
}
bool empty()
{
return frontIndex == backIndex;
}
bool full()
{
// backIndex의 다음 위치가 frontIndex가 가리키는 공백인 경우 full 상태로 생각
return frontIndex == (backIndex + 1) % MAX_SIZE;
}
int front()
{
if (empty()) return -1;
else return elements[(frontIndex + 1) % MAX_SIZE];
}
int back()
{
if (empty()) return -1;
else return elements[backIndex];
}
};
int main()
{
// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
Deque dq(N);
vector<int> output;
for (int i = 0; i < N; i++)
{
int command;
cin >> command;
switch (command)
{
case 1:
int x;
cin >> x;
dq.push_front(x);
break;
case 2:
int y;
cin >> y;
dq.push_back(y);
break;
case 3:
output.push_back(dq.pop_front());
break;
case 4:
output.push_back(dq.pop_back());
break;
case 5:
output.push_back(dq.size());
break;
case 6:
output.push_back(dq.empty());
break;
case 7:
output.push_back(dq.front());
break;
case 8:
output.push_back(dq.back());
break;
default:
break;
}
}
for (int i = 0; i < output.size();i++)
{
cout << output[i] << "\n";
}
return 0;
}<풀이과정>
- Deque
1. 원소들을 담을 배열의 주소를 가리킬 포인터 변수 elements, 맨 앞의 인덱스 번호인 frontIndex, 맨 뒤의 인덱스 번호인 backIndex, 배열의 최대 크기를 나타내는 MAX_SIZE 변수를 private으로 선언한다.
2. public으로 함수들을 아래와 같은 함수들을 선언한다.
3. Deque(int n)
3-1. 생성자의 인수로 n을 받아와 n의 크기의 새로운 배열을 만들고 elements가 해당 배열을 가리키게 함
3-2. frontIndex와 backIndex를 0으로 초기화 시킴
3-3. MAX_SIZE를 n으로 초기화 시킴
4. push_front(int x)
4-1. 앞에 원소를 삽입하는 함수
4-2. elements의 frontIndex번째 인덱스에 x를 삽입
4-3. frontIndex를 1감소 시켜주는데 음수가 될 경우를 생각해 MAX_SIZE를 더하고 더해서 나온 값을 MAX_SIZE로 나누었을때 나오는 나머지값을 frontIndex에 대입해줌
5. push_back(int x)
5-1. 뒤에 원소를 삽입하는 함수
5-2. backIndex를 1증가 시켜주는데 배열의 크기를 넘어갈 경우를 생각해 증가시킨 수를 MAX_SIZE로 나누었을때의 나머지를 backIndex에 대입해준다.
5-3. 대입한 backIndex 값을 인덱스로하는 자리에 x를 넣어준다.
6. pop_front()
6-1. 맨 앞의 원소를 빼내어 출력하는 함수
6-2. 비었을 경우에는 -1을 리턴
6-3. 그렇지 않을 경우, frontIndex는 항상 공백을 가리키고 이전의 원소가 현재 맨 앞의 원소이므로 frontIndex를 해당 값으로 바꿔주고 바꾼 frontIndex번째 원소를 elements에서 찾아 리턴해줌
7. pop_back()
7-1. 맨 뒤의 원소를 빼내어 출력하는 함수
7-2. 비었을 경우에는 -1을 리턴
7-3. 그렇지 않을 경우, backIndex는 해당 자리가 마지막 원소의 자리인데, 바로 리턴을 해주면 backIndex의 값을 변경시킬 수 없으므로 backIndex의 값을 임시로 curBackIndex에 저장해놓고 backIndex의 값을 -1을 해준 뒤 curBackIndex번째 원소를 elements에서 찾아 출력한다.
8. size()
8-1. 현재 elements에 들어있는 원소들의 갯수를 출력해주는 함수
8-2. backIndex에서 frontIndex값을 빼준 값을 리턴하는데 음수가 나올 경우를 생각해 해당 값에 MAX_SIZE를 더해주고 더한 값을 MAX_SIZE로 나누었을때 나오는 나머지를 리턴한다.
9. empty()
9-1. elements가 비었는지 판단하는 함수
9-2. 초기의 값인 frontIndex와 backIndex가 0으로 같을 경우에만 빈 경우이므로 frontIndex와 backIndex가 같은지에 대한 결과를 리턴함
10. full()
10-1. elements가 가득 차 있는지 판단하는 함수
10-2. deque에서 가득 차 있는 경우는 backIndex의 다음 인덱스가 frontIndex가 가리키는 공백을 가리킬 때를 말한다.
10-3. 즉, 특이하게도 deque는 한 칸만 남아 비어있는 경우를 가득찬 경우로 판단한다. (한 칸을 남기지 않으면 frontIndex와 backIndex가 같아져서 empty()의 경우와 같게 되므로 이를 구분하기 위해 한 칸을 남긴 것임)
10-4. 그러므로 frontIndex가 backIndex의 다음 인덱스인 backIndex + 1와 비교하는데 이 경우에도 +1한 backIndex가 배열의 크기를 넘어갈 경우를 대비하여 MAX_SIZE로 나눈 나머지 값을 이용하여 비교를 진행하고 결과 값을 리턴해준다.
11. front()
11-1. 맨 앞의 원소를 출력해주는 함수(배열에서 빠지지는 않음)
11-2. 비어있는 경우에는 -1을 리턴함
11-3. 그렇지 않은 경우, frontIndex의 다음 인덱스 값을 배열을 넘어가는 경우를 고려해 MAX_SIZE로 나눈 나머지 값을 이용하여 elements의 해당 인덱스의 값을 리턴함
12. back()
12-1. 맨 뒤의 원소를 출력해주는 함수(배열에서 빠지지는 않음)
12-2. 비어있는 경우에는 -1을 리턴함
12-3. 그렇지 않은 경우, backIndex에 해당되는 값을 인덱스로 가지는 elements의 값을 리턴함
- Main
1. N을 입력받고, 앞서 선언한 구조체 Deque dq를 N의 크기로 선언하고, 결과값을 담을 output 벡터를 정의한다.
2. N만큼 반복하며 명령어 command를 int형으로 입력받고, 해당 값을 이용해 switch문을 돌린다.
3. command가 1 또는 2인 경우 값을 넣어주는 작업이므로 추가적으로 변수를 입력받아 해당 함수를 실행한다.
4. 이외의 경우 output 벡터에 해당 작업에 맞는 함수를 실행하여 얻은 결과 값을 넣어준다.
5. 모든 명령어 입력이 끝난 뒤, 함수들의 실행 결과 값들이 저장된 output의 원소들을 하나씩 출력해준다.
<코멘트>
덱을 직접 구현하여 풀어보았다!
덱이라는 자료구조가 아직 어색했어서 자료를 찾아보면서 진행했는데 개념적인 부분이 조금 어려웠다.
원형큐의 확장버전이라고 생각하면 될 것 같다!
<제출결과>
