https://www.acmicpc.net/problem/10866
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
문제 해결 과정
착안
덱(deque) 자료 구조는 double-ended queue를 의미하며, 양방향에서 데이터의 삽입 및 출력이 가능한 큐 자료 구조이다. 큐를 구현할 때와 마찬가지로 데이터의 입출력 과정에서 Front와 Rear 변수를 제어함으로써 덱 자료 구조를 표현하고자 하였다.
편의상 배열 형태로 구현하고자 하였고, Front, Rear 변수를 각각 현재 존재하는 데이터의 가장 앞, 뒤 요소의 인덱스를 나타내도록 사용하였다. 양방향에서 데이터의 삽입과 출력이 가능한 점을 고려해 문제의 요구 수준을 만족하는 충분히 큰 배열을 선언한 다음 배열의 가운데 인덱스부터 시작할 수 있도록 Front, Rear 변수를 초기화하고자 하였다. 이때 덱이 비어있는 상태는 Rear의 값이 Front보다 작은 상태로 표현하고자 하였다.
양방향으로 확장이 되는 형태이므로, 데이터의 입출력에 따라 다음과 같이 작동하도록 구상하였다.
- push_front(): Front의 값을 감소한 뒤 데이터를 Front의 위치에 삽입
- push_back(): Rear의 값을 증가한 뒤 데이터를 Rear의 위치에 삽입
- pop_front(): 현재 Front 위치에 존재하는 데이터를 출력한 뒤 Front의 값을 증가
- pop_back(): 현재 Rear 위치에 존재하는 데이터를 출력한 뒤 Rear의 값을 감소
pop_front(), pop_back()을 통해 실제로 Front 또는 Rear 위치에 있는 요소를 배열에서 삭제할 필요까지는 없기 때문에, 단순히 출력만 수행한 뒤 Front, Rear의 값을 제어하여 pop을 수행한 값에는 접근할 수만 없도록 구현하고자 하였다.
구현
앞에서 구상한 것과 같이 프로그래밍하였는데, 문제에서 요구하는 것과 같이 동작을 수행했을 때 인덱스가 배열 범위를 초과하지 않도록 배열 크기를 선언하고 Front 및 Rear 변수를 제어하는 데에 중점을 두어 구현하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
#include <iostream>
using namespace std;
int Deque[19998];
int Front = 10000;
int Rear = Front - 1;
int Size;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
while (N--)
{
string Op;
cin >> Op;
if (Op == "push_front")
{
cin >> Deque[--Front];
Size++;
}
else if (Op == "push_back")
{
cin >> Deque[++Rear];
Size++;
}
else if (Op == "pop_front")
{
if (Rear < Front)
cout << "-1\n";
else
{
cout << Deque[Front++] << "\n";
Size--;
}
}
else if (Op == "pop_back")
{
if (Rear < Front)
cout << "-1\n";
else
{
cout << Deque[Rear--] << "\n";
Size--;
}
}
else if (Op == "size")
cout << Size << "\n";
else if (Op == "empty")
cout << (Rear < Front) << "\n";
else if (Op == "front")
{
if (Rear < Front)
cout << "-1\n";
else
cout << Deque[Front] << "\n";
}
else if (Op == "back")
{
if (Rear < Front)
cout << "-1\n";
else
cout << Deque[Rear] << "\n";
}
}
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 14891번: 톱니바퀴 (0) | 2023.07.03 |
---|---|
[Baekjoon] 11279번: 최대 힙 (0) | 2023.07.02 |
[Baekjoon] 4134번: 다음 소수 (0) | 2023.07.02 |
[Baekjoon] 14889번: 스타트와 링크 (0) | 2023.07.02 |
[Baekjoon] 2630번: 색종이 만들기 (0) | 2023.06.29 |
댓글